## 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 = {}, 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 ={}, 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;
}
};
``````