There are n users on a social media website. You are given an integer array ages, where ages[i] is the age of the i-th user.

If any of the following conditions is true, user x will not send a friend request to user y (x != y):

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 friend request to y, y does not have to send one to x. Also, a user will not send a friend request to themselves.

Return the total number of friend requests sent on the social media website.

Example 1:

Input:ages = [16,16]
Output:2
Explanation:The two people send friend requests to each other.

Example 2:

Input:ages = [16,17,18]
Output:2
Explanation:The friend requests are 17 -> 16 and 18 -> 17.

Example 3:

Input:ages = [20,30,100,110,120]
Output:3
Explanation:The friend requests are 110 -> 100, 120 -> 110, and 120 -> 100.

Constraints:

n == ages.length
1 <= n <= 2 * 10⁴
1 <= ages[i] <= 120

Analysis
#

At first glance this problem seems easy, but it is more subtle than it looks. Problems defined by conditions often invite a brute-force pairwise comparison with O(n^2) complexity, but that approach is clearly not suitable here.

Instead, look for conditions that can be exploited. There are three of them, and it is important to read their logic carefully: if any one condition is true, the request is not sent. Therefore, a request is sent only when all three conditions are false. The first condition means that y must be greater than 0.5x + 7; the second means that y must be less than or equal to x; and the third means that y > 100 and x < 100 must not both be true.

Therefore, the input order does not matter. Count how many users have each age in an array, then perform the remaining calculations.

Next use a two-pointer approach. After organizing the data, the ages are ordered, and for a specific sender age, the possible recipient ages lie within a certain interval. These intervals can overlap, so use prefix sums to perform the calculation.

impl Solution {
    pub fn num_friend_requests(ages: Vec<i32>) -> i32 {
        let (mut cnt, mut cs, mut res) = ([0; 121], [0; 121], 0);
        for age in ages { cnt[age as usize] += 1; }
        for i in 1..=120 { cs[i] = cs[i - 1] + cnt[i]; }
        for i in 15..=120 { res += cnt[i] * (cs[i] - cs[i / 2 + 7] - 1); }
        res
    }
}

The fourth line counts users by age, the fifth line computes the prefix sums, and the sixth line computes the final result. For a sender whose age is in the range 15–120, if the age is i, that sender can send friend requests to users whose ages lie in the range (i~i/2+7).

Analysis#

Analysis
#