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] &lt;= 0.5 * age[x] + 7
	age[y] &gt; age[x]
	age[y] &gt; 100 &amp;&amp; age[x] &lt; 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.

&nbsp;
Example 1:

Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.


Example 2:

Input: ages = [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -&gt; 16, 18 -&gt; 17.


Example 3:

Input: ages = [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -&gt; 100, 120 -&gt; 110, 120 -&gt; 100.


&nbsp;
Constraints:


	n == ages.length
	1 &lt;= n &lt;= 2 * 104
	1 &lt;= ages[i] &lt;= 120


class Solution:
    """
    approach:
    we can try solving this problem by finding the valid age group for each age
    sort the array in descending order
    iterate from right to left
    for current age, find the valid agegroup to which the current age person will send a request
    we can use binary search for that
    if current age is x, then valid age group to send a request is:
    x*0.5 + 7 < age(y) <= x
    we can find the left limit using binary search
    """
    def binary_search(self, arr, low, high, value):
        if low > high:
            return high
        mid = (low + high) // 2
        if arr[mid] > value:
            return self.binary_search(arr, low, mid-1, value)
        else:
            return self.binary_search(arr, mid+1, high, value)

    def numFriendRequests(self, ages: List[int]) -> int:
        ages = sorted(ages)
        total_count = 0
        for i in range(len(ages)-1, -1, -1):
            if i+1 < len(ages) and ages[i] == ages[i+1]:
                total_count+= prev_count
                continue

            prev_count = 0
            lower_limit = 0.5 * ages[i] + 7
            index = self.binary_search(ages, 0, i-1, lower_limit)
            prev_count = i - (index+1)
            total_count+=prev_count
        return total_count
class Solution {
    static int upperBound(int arr[], int target) {
        int l = 0, h = arr.length - 1;
        for (; l <= h;) {
            int mid = (l + h) >> 1;
            if (arr[mid] <= target)
                l = mid + 1;
            else
                h = mid - 1;
        }
        return l;
    }
    public int numFriendRequests(int[] ages) {
        long ans = 0;
        Arrays.sort(ages);
		// traversing order doesn't matter as we are doing binary-search in whole array
		// you can traverse from left side also
        for(int i = ages.length - 1;i >= 0;--i){
            int k = upperBound(ages,ages[i] / 2 + 7);
            int t = upperBound(ages,ages[i]);
            ans += Math.max(0,t - k - 1);
        }
        return (int)ans;
    }
}
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        sort(ages.begin(), ages.end());
        int sum = 0;
        for (int i=ages.size()-1; i>=0; i--) {
            int cutoff = 0.5f * ages[i] + 7;
            int j = upper_bound(ages.begin(), ages.end(), cutoff) - ages.begin();
            int k = upper_bound(ages.begin(), ages.end(), ages[i]) - ages.begin();
            sum += max(0, k-j-1);
        }
        return sum;
    }
};
var numFriendRequests = function(ages) {
    const count = new Array(121).fill(0);

    ages.forEach((age) => count[age]++);

    let res = 0; // total friend request sent
    let tot = 0; // cumulative count of people so far

    for (let i = 0; i <= 120; i++) {

        if (i > 14 && count[i] != 0) {
            const limit = Math.floor(0.5 * i) + 7;
            const rest = tot - count[limit];

            res += (count[i] * rest); // current age group send friend request to other people who are within their limit
            res += (count[i] * (count[i] - 1)); // current age group send friend request to each other
        }

        tot += count[i];
        count[i] = tot;
    }

    return res;
};
Friends Of Appropriate Ages