825. Friends of Appropriate Ages

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

• age[B] <= 0.5 * age[A] + 7

• age[B] > age[A]

• age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

Input: [16,16]

Output: 2

Explanation: 2 people friend request each other.

Example 2:

Input: 
[16,17,18]

Output: 2

Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: 
[20,30,100,110,120]

Output: 
Explanation: 
Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

• 1 <= ages.length <= 200 00.

• 1 <= ages[i] <= 120.

Thoughts:

1. 0.5 A + 7 < B <= A : so A >= 15; the three condition is redundant

Code: O(n + r * r), r: age range

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int a[121] = {}, res = 0;
        for (auto age : ages) a[age]++;
        for (auto A = 15; A <= 120; A++)
            for(int B = 0.5 * A + 8; B <= A; B++){
                res += a[B] * (a[A] - (A == B));
            }

        return res;
    }
};

Code: O(n + m), r: age range

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int a[121] ={}, res = 0;
        for (auto age : ages) a[age]++;
        for (int A = 15, lower = 15, acc = 0; A <= 120; acc += a[A], res+= a[A++] * (acc - 1))
            // meet the first constraint by removing out those low ages that does not qualify
            while(lower <= 0.5 * A + 7) acc -=  a[lower++];

        return res;
    }
};