825. Friends Of Appropriate Ages

Problem Statement

link: LeetCode.cn LeetCode There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the ith person.

A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true:

age[y] <= 0.5 * age[x] + 7 age[y] > age[x] age[y] > 100 && age[x] < 100 Otherwise, x will send a friend request to y.

Note that if x sends a request to y, y will not necessarily send a request to x. Also, a person will not send a friend request to themself.

Return the total number of friend requests made.

Example:

Input: ages = [16,16] Output: 2

Input: ages = [16,17,18] Output: 2

Constraints: n == ages.length 1 <= n <= 2 * 104 1 <= ages[i] <= 120

Solution Approach

The solution uses counting and prefix sums to efficiently calculate the total number of valid friend requests by checking age-related conditions for each person.

Algorithm

1. Counting Age Frequency: Use a frequency array to count the occurrences of each age, which allows efficient calculation of potential friend requests.
2. Prefix Sum Calculation: Create a prefix sum array to quickly determine the cumulative number of people with ages less than or equal to a given age, aiding in range queries.
3. Range-based Friend Requests: Iterate through possible ages and calculate valid friend requests using the conditions, subtracting inappropriate requests using the prefix sum array.

Implement

    class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        # Count the number of people for each age from 0 to 120
        cnt = [0] * 121
        for age in ages:
            cnt[age] += 1
        
        # Calculate the cumulative number of people up to each age
        pre = [0] * 121
        for i in range(1, 121):
            pre[i] = pre[i - 1] + cnt[i]
        
        ans = 0
        # Iterate through possible ages from 15 to 120
        for i in range(15, 121):
            if cnt[i] > 0:
                # Calculate the lower bound for the age of the person who can receive a friend request
                bound = int(i * 0.5 + 7)
                # Calculate the number of valid friend requests for the current age
                ans += cnt[i] * (pre[i] - pre[bound] - 1)
        
        return ans

 

    
    

Twitter  facebook  Email