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: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

 
Notes:

1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

Difficulty: interview

Starter code:

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        

Solutions:
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0]*121
        s = [0]*121
        for a in ages:
            count[a]+=1
        for i in range(1,121):
            s[i] = s[i-1]+count[i]
        res = 0
        for i in range(15,121):
            edge = i//2+7
            num = s[i]-s[edge]
            res+=count[i]*num-count[i]
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        # Note age[B] > 100 && age[A] < 100 is redundant since we have age[B] > age[A]
        def wantToRequest(A, B):
            return not(B <= 0.5 * A + 7 or B > A)
        
        count = Counter(ages)
        ans = 0
        ages = [*sorted(count.keys())]
        
        for i, a in enumerate(ages):
            for j in range(0, i+1):
                b = ages[j]
                if wantToRequest(a, b):
                    ans += count[a] * count[b] if a != b else count[a] * (count[b] - 1)
        
        return ans


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        sum = 0
        counts = collections.Counter(ages)
        ages = sorted(counts.keys())
        for A in range(0,len(ages)):
            for B in range(0,len(ages)):
                condition1 = ages[B] <= 0.5 * ages[A] + 7
                condition2 = ages[B] > ages[A]
                condition3 = ages[B] > 100 and ages[A] < 100
                if not (condition1 or condition2 or condition3):
                    if A!=B:
                        sum += counts[ages[A]]*counts[ages[B]]
                    else:
                        sum += (counts[ages[A]]-1)*counts[ages[B]]
        return sum

class Solution(object):
    def numFriendRequests(self, ages):
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0 for _ in range(121)]
        for a in ages:
            count[a] += 1
        ans = 0
        for a, cnt_a in enumerate(count):
            for b, cnt_b in enumerate(count):
                if a <= 0.5 * b + 7:
                    continue
                if a > b:
                    continue
                if a > 100 and b < 100:
                    continue
                ans += cnt_a * cnt_b
                if a == b:
                    ans -= cnt_a
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def request(a,b):
            return not (b <= 0.5*a +7 or b > a or (b>100 and a < 100))
        c = collections.Counter(ages)
        return sum( request(a,b) * c[a]* (c[b] - (a==b)) for a in c for b in c)


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        if not ages:
            return 0
        
        freq = Counter(ages)
        
        def can_request(a, b):
            return not (b <= 0.5 * a + 7 or b > a or b > 100 and a < 100)
            
        ans = 0
        for a1 in range(1, 121):
            for a2 in range(1, 121):
                if can_request(a1, a2):
                    ans += (freq[a1] * freq[a2]) if a1 != a2 else (freq[a1] * (freq[a1]-1))     
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        if not ages or len(ages) < 2: return 0
        res=0
        d=[0]*121
        for age in ages:
            d[age]+=1
        for A in range(121):
            for B in range(121):
                count=0
                if B<=A and B> A//2 +7:
                    count+=d[A]*d[B]
                if A==B and count:
                    count-=d[A]
                res+=count
        return res


'''
    a -> b if
    a = 10
    b = 12
    b > a
    a = 50
    b = 30
    
    a = 50
    b = 50
    .5 * 50 + 7 = 32
    a -> b if a >= b and b > 0.5 * a + 7
    a > 0.5 * a + 7
    0 > 0.5*a + 7 - a
    0 > 7 - .5a
    .5a > 7
    a > 14
    mutual friend request if a > 14
    
    [20, 20, 18, 18, 14, 12 ]
    15 * .5 + 7 = 14.5
    14 * .5 + 7 = 14
    12 * .5 + 7 = 13
    20 * .5 + 7 = 17
    18 * .5 + 7 = 16
    {
    16: 1
    17: 2
    18: 4
    19: 2
    20: 4
    }
    num_reqs = 8, 
    [102, 98, 59]
    102 * .5 + 7 = 58
    59
    98 * .5 + 7 = 56
    {56: 1, 57: 1, 58: 1, 59: 2,...98: 3,...102: 2}
    3
    O(nlogn)
    O(1)
'''

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def invert(a):
            return -1 * a
        ages.sort(key=invert)
        age_request_map = collections.defaultdict(int)
        num_requests = 0
        for age in ages:
            if age <= 14:
                break
            num_requests += age_request_map[age]
            # need to double count for same ages
            age_request_map[age] += 1
            lowest_age = floor(age * .5 + 7) + 1
            for i in range(lowest_age, age + 1):
                age_request_map[i] += 1
        return num_requests

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        
        age_dic = {age: ages.count(age) for age in range(1,121)}
        
        
        pairs = 0
        for A in range(1,121):
            for B in range(1,121):
                if B <= 0.5 * A + 7:
                    continue
                elif B > A:
                    continue 
                elif B > 100 and A < 100:  
                    continue 
                
        
                else:
                    pairs += age_dic[A] * age_dic[B]
                    if A == B:
                        pairs -= age_dic[A]
        return pairs
        
                


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        # time O(A^2+n); space O(A)
        age_cnt = [0] * 121
        for age in ages:
            age_cnt[age] += 1
        
        res = 0
        for ageA, cntA in enumerate(age_cnt):
            for ageB, cntB in enumerate(age_cnt):
                if ageB <= (0.5 * ageA + 7) or ageB > ageA or (ageB > 100 and ageA < 100):
                    continue
                res += (cntA * cntB)
                if ageA == ageB:
                    res -= cntA
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counter = Counter(ages)
        
        ages = list(counter.keys())
        res = 0
        for a in ages:
            for b in ages:
                if b <= 0.5*a + 7:
                    continue
                if b > a:
                    continue
                if b > 100 and a < 100:
                    continue
                    
                if a == b:
                    res += counter[a]*(counter[a]-1)
                else:
                    res += counter[a]*counter[b]
    
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages = sorted(ages)
        res = 0
        prev = None
        for i in range(len(ages) - 1, -1, -1):
            if i == len(ages) - 1 or ages[i] != ages[i + 1]:
                prev = i
            low ,right = 0 ,prev - 1
            while low < right:
                mid = (low + right)//2
                if ages[mid] <= 0.5*ages[i] + 7:
                    low = mid + 1
                else:
                    right = mid
            if ages[low] >  0.5 * ages[prev] + 7:
                res += (prev - low)
        return res
                    


from collections import Counter
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def is_valid(a, b):
            return not any([
                b <= 0.5 * a + 7,
                b > a,
                b > 100 and a < 100
            ])
        counts = Counter(ages)
        ages = list(counts)
        requests = 0
        for i in range(len(ages)):
            for j in range(len(ages)):
                count = (
                    counts[ages[i]] * (counts[ages[i]] - 1) if i == j
                    else counts[ages[i]] * counts[ages[j]]
                )
                requests += int(is_valid(ages[i], ages[j])) * count
        return requests

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def counting_sort():
            counts = 120 * [0]
            for i in range(len(ages)):
                counts[ages[i] - 1] += 1
            s = []
            for i in range(len(counts)):
                s += [i + 1] * counts[i]
            return s
        ages = counting_sort()
        res = 0
        prev = None
        for i in range(len(ages) - 1, -1, -1):
            if i == len(ages) - 1 or ages[i] != ages[i + 1]:
                prev = i
            low ,right = 0 ,prev - 1
            while low < right:
                mid = (low + right)//2
                if ages[mid] <= 0.5*ages[prev] + 7:
                    low = mid + 1
                else:
                    right = mid
            if ages[low] >  0.5 * ages[prev] + 7:
                res += (prev - low)
        return res
                    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def counting_sort():
            nonlocal ages
            counts = 120 * [0]
            for i in range(len(ages)):
                counts[ages[i] - 1] += 1
            ages = []
            for i in range(len(counts)):
                ages += [i + 1] * counts[i]
        counting_sort()
        res = 0
        prev = None
        for i in range(len(ages) - 1, -1, -1):
            if i == len(ages) - 1 or ages[i] != ages[i + 1]:
                prev = i
            low ,right = 0 ,prev - 1
            while low < right:
                mid = (low + right)//2
                if ages[mid] <= 0.5*ages[prev] + 7:
                    low = mid + 1
                else:
                    right = mid
            if ages[low] >  0.5 * ages[prev] + 7:
                res += (prev - low)
        return res
                    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages = sorted(ages)
        res = 0
        prev = None
        for i in range(len(ages) - 1, -1, -1):
            if i == len(ages) - 1 or ages[i] != ages[i + 1]:
                prev = i
            low ,right = 0 ,prev - 1
            while low < right:
                mid = (low + right)//2
                if ages[mid] <= 0.5*ages[i] + 7:
                    low = mid + 1
                else:
                    right = mid
            if ages[low] >  0.5 * ages[i] + 7:
                res += (prev - low)
        return res
                    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages = sorted(ages)
        res = 0
        prev = None
        for i in range(len(ages) - 1, -1, -1):
            if i == len(ages) - 1 or ages[i] != ages[i + 1]:
                prev = i
            low ,right = 0 ,prev - 1
            while low < right:
                mid = (low + right)//2
                if ages[mid] <= 0.5*ages[prev] + 7:
                    low = mid + 1
                else:
                    right = mid
            if ages[low] >  0.5 * ages[prev] + 7:
                res += (prev - low)
        return res
                    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = collections.Counter(ages)
        ans = 0
        for age in ages:
            cnt[age] -= 1
            left, right = age // 2 + 8, age
            ans += sum(cnt[age] for age in range(left, right + 1))
            cnt[age] += 1
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def req(A, B):
            if B<=(0.5*A+7) or B>A or (B>100 and A<100):
                return False
            return True
        
        cnt = Counter(ages)
        ans = 0
        for i in cnt:
            if cnt[i] > 1 and req(i, i):
                ans += cnt[i]*(cnt[i]-1)
            
            for j in cnt:
                if i != j and req(i, j):
                    ans += cnt[i]*cnt[j]
        return ans

from collections import Counter
import math

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counter = Counter(ages)
        count = 0
        
        for age_A in ages:
            max_age = age_A
            min_age = 0.5 * age_A + 7
            for age_B in range(math.floor(min_age)+1, max_age+1):
                count += counter[age_B]
                if age_B == age_A:
                    count -= 1
        
        return count
                


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

            temp_count, current = 0, i-1
            age = 0.5 * ages[i] + 7
            while current >= 0 and ages[current] > age:
                temp_count += 1
                current = current - 1

            count = count + temp_count

        return count
                


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        res = 0
        i = 0
        while i<len(ages):
            if ages[i]<=14:
                i+=1
            else:
                break
        if i==len(ages):
            return 0
        leftmost = i
        for i in range(leftmost,len(ages)):
            left,right = leftmost,i-1
            edge = ages[i]*0.5+7
            while left<=right:
                m = (left+right)//2
                if ages[m]<=edge:
                    left = m+1
                else:
                    right = m-1
            res+=i-left
            # find same age:
            left,right = i+1,len(ages)-1
            while left<=right:
                m = (left+right)//2
                if ages[m]<=ages[i]:
                    left = m+1
                else:
                    right = m-1
            left-=1
            res+=left-i
        return res
                


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ageIdx = defaultdict(list)
        for i,age in enumerate(ages):
            ageIdx[age].append(i)
            
        count = 0
        for age in ageIdx:
            lowerBound = int((1/2)*age)+7+1
            upperBound = age
            for A in ageIdx[age]:
                for candAge in range(lowerBound,upperBound+1):
                    if candAge in ageIdx:
                        if candAge != age:
                            count += len(ageIdx[candAge])
                        else:
                            count += len(ageIdx[candAge]) - 1
        
        return count

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        age_range = [0] * 121
        
        ages = sorted(ages)
        
        ans = 0
        
        for age in ages:
            
            for i in range(age - 1, -1, -1):
                
                if i <= 0.5 * age + 7:
                    break
                                        
                ans += age_range[i]
            
#             it is tricky here, becareful
            if age > 0.5 * age + 7:
                ans += age_range[age] * 2
                        
            age_range[age] += 1
            
        return ans


'''
Start: 2:25 p.m.
'''

'''
- Visualize everything.
- Work with concrete examples.
- Commit to a hunch. Crystallize it into an approach that can be evaluated (validated/invalidated). OK if approach seems unlikely to work.
'''

'''
[16, 16]

A will not send FR to someone who is older (same age OK).
=> sort the array

A will not send FR to someone who is \"much\" younger.
If A is under 100, he will not send FR to anyone over 100.
Not FR self.
'''

'''
Brute-force: evaluate every pair
Time: O(n^2)
Space: O(1)
'''

'''
- A will not friend anyone older so no need to look forward, only backward.

Time:O(n log n)
Space: O(n)

- Sort
- For each num, compute minimum bound, BS.

lb = 16/8 + 7 = 15

[16,17,18]
 i
 
 17/2 = 8.5 ~= 8
 15
'''

'''
Test Cases
no numbers before i (works)
[5]
 i
 
 nothing >= lower bound (works)
 [1, 2, 50]
        i
        
lb = 32
multiple occurrences of lb (works)
[1, 2, 32, 32, 40, 41, 50]
       m
 l
       r
                       i
       ret
               
lb = 32
only > lb (works)
[1, 2, 40, 41, 50] 
               i
       ret
       
[40, 41, 50] (works)
         i
 ret
'''

'''
PASS
[1, 2, 32, 32, 40, 41, 50]
[1, 2, 50]
[1, 2, 40, 41, 50] 
[40, 41, 50]
[16,16]
'''

class Solution:
    def firstLTE(self, lowerBound, ages, endIndex):
        if endIndex < 0:
            return 0
        
        l = 0
        r = endIndex
        
        while l < r:
            m = (l + r) // 2  # originally ages[l], ages[r] instead of l, r -- I'm very compromised today.
            
            if ages[m] <= lowerBound:
                l = m + 1
            else:
                r = m
                
        if l <= r and ages[l] > lowerBound:
            return l
                
        return endIndex + 1
    
    def findEarliest(self, key, ages, endIndex):
        if endIndex < 0:
            return -1
        
        l = 0
        r = endIndex
        
        while l < r:
            m = (l + r) // 2
            
            if ages[m] >= key:
                r = m
            else:
                l = m + 1
        
        if l <= endIndex and ages[l] == key:
            return l
        
        return -1
    
    '''
    [16, 16]
     l
     r
         i
      
     lowerBound = 23
    [1, 2, 32, 32]
        m        
           l
           r
    '''
    
    def numFriendRequests(self, ages: List[int]) -> int:
        if not ages:
            return 0
        
        numRequests = 0
        
        ages.sort()  # O(n log n)/O(n)
        
        for i, a in enumerate(ages):
            lowerBound = a*0.5 + 7  # divided instead of multiplied originally
            startIndex = self.firstLTE(lowerBound, ages, i - 1)
            #print('i = {}, startIndex = {}, delta = {}'.format(i, startIndex, i - startIndex))
            numRequests += i - startIndex
            
            if a > lowerBound:
                startIndex = self.findEarliest(a, ages, i - 1)
                if startIndex >= 0 and startIndex < i:
                    numRequests += i - startIndex
        
        return numRequests
    
'''
[73,106,39,6,26,15,30,100,71,35,46,112,6,60,110]
'''   
        


import collections

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_count = collections.Counter(ages)
        res = 0
        for age_A, count_A in age_count.items():
            for age_B, count_B in age_count.items():
                if not age_B <= age_A * 0.5 + 7 and not age_B > age_A:
                    if age_A == age_B:
                        res += count_A * (count_A - 1)
                    else:
                        res += count_A * count_B
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages = sorted(ages)
        print(ages)
        def bound(a):
            low = a//2 + 8
            hi = a
            return (min(low, a), hi)
        def getlow(v):
            lo, hi = 0, len(ages)
            while lo < hi:
                mid = (lo + hi)//2
                if ages[mid] >= v: hi = mid
                else: lo = mid + 1
            return hi
        def getupper(v):
            lo, hi = 0, len(ages)
            while lo < hi:
                mid = (lo + hi)//2
                if ages[mid] <= v:
                    lo = mid + 1
                else:
                    hi = mid
            return hi-1
        
        count = 0
        for i in range(len(ages)):
            if ages[i] <= 14: continue
            minv, maxv = bound(ages[i])
            c= getupper(maxv) - getlow(minv) 
            # print(i,\"  :\",c, getlow(minv), getupper(maxv) )
            count += c
          
        p = 115
        # print( getlow(p), getupper(p))
        return count

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        ages = sorted(ages, reverse=True)
        n = len(ages)
        
        dp = [0] * n
        res = 0
        
        for i in range(n):
            
            if i > 0 and ages[i] == ages[i-1]:
                dp[i] = dp[i-1]
                res += dp[i]
                continue
            
            for j in range(i+1, n):
                if ages[j] <= 0.5 * ages[i] + 7:
                    break
                else:
                    dp[i] += 1
            
            res += dp[i]
        
        return res
        


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        if ages == []:
            return 0
        ages.sort()
        res = 0
        for i in range(len(ages) - 1, -1, -1):
            if ages[i] < 15:
                break
            age = ages[i]
            left = self.binary_search_left(ages, 0, i, age // 2 + 8)
            right = self.binary_search_right(ages, i, len(ages) - 1, age)
            #print(left, right)
            res += max(0, right - left)
        return res

    def binary_search_left(self, ages, start, end, target):
        while start + 1 < end:
            mid = (start + end) // 2
            if ages[mid] < target:
                start = mid
            else:
                end = mid
        
        if ages[start] >= target:
            return start
        if ages[end] >= target:
            return end
        return -1

    def binary_search_right(self, ages, start, end, target):
        while start + 1 < end:
            mid = (start + end) // 2
            if ages[mid] <= target:
                start = mid
            else:
                end = mid
        if ages[end] <= target:
            return end
        if ages[start] <= target:
            return start
        return -1

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()

        def count(a):
            i, j = 0, len(ages) - 1

            while i < j:
                k = (i + j + 1) // 2
                if ages[k] <= a:
                    i = k
                else:
                    j = k - 1

            u = i

            v = a // 2 + 7
            i, j = 0, len(ages) - 1

            while i < j:
                k = (i + j) // 2
                if ages[k] <= v:
                    i = k + 1
                else:
                    j = k

            l = i

            return u - l if l <= u else 0

        return sum(count(a) for a in ages)



class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = 0
        ages.sort()
        for i, age in enumerate(ages):
            minTarget = (age // 2) + 7
            maxTarget = age
            minIdx = self.binFinder(ages, minTarget)
            maxIdx = self.binFinder(ages, maxTarget)
            count += max(0, maxIdx - minIdx -1)
        return count
    def binFinder(self, arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = left + ((right - left)//2)
            if arr[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return left

# id(index) -> age
# age1 <= 7 + 0.5 age2
# age1 > age2
#age1 > 100 and age b < 100
# no selfloop,
#A request does not mean B reqeust A

def count_smaller_than(ages, target): # 1,15,17
    left = 0 # 1
    right = len(ages) - 1 # 0
    
    # 1 5 6 11 all elements smaller than  target 7
    # 1  [5] [6  [11] L = 3 R= 3 --> L = 3 R = 2 L -1
    #           L = 4 R = 3
  # [5] [6] 11 12 0 -> 0 0 -> -1
    # 5 6 | [6] 6 7 
    while left <= right:
        mid = left+(right-left)//2 # 15 # 1
        if ages[mid] < target: # 15 < 15
            left = mid+1        
        # elif ages[mid] == target and ages[a_index] == ages[mid]:
        #     right = mid - 1
        else:# ages[mid] >= target:
            right = mid -1 # 0 
            
    return left # 0 - 1
            
    # edge case [16,16]
    
    

import math
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        #brute force
        #we loop on friends A
            # we loop again B
                # increment if a request B or B requests A
                
                # time o(n^2), space o(1)
                
        #A < B
        # --> check only once not twice because second one is always false
        #whenever B > 100 and A < 100 --> recursve
        # O(N^2)
        
        #A --> 10 ---> [maximum length we make friends of] --> we search for that in the array and then we return
        # nlogn --> sort
        # n * logn (Binary search) to get the count
        
        ages.sort() # sort in ascending order
        friend_requests = 0
        
        #[1,17,18]
        for i in range(len(ages)):
            age_a = ages[i]  # 16
            
            # max_age_b = max(age_a,) # age_a = 9 -> 4.5 + 7 -> 11.5
            # 0 
            
            # 0 1 2 3 
            # 1 * 0.5 + 7 -> 7
            smaller_than = count_smaller_than(ages, math.floor(0.5 * age_a) + 8) # these are the ones to exclude, if it's
            smaller_than_i = count_smaller_than(ages, age_a+1)
            
            a_requests = max(0, smaller_than_i - 1 - smaller_than)  #(itself)
            
            friend_requests += a_requests
            
        return friend_requests
            


class Solution:
    
    def B_search(self, nums, target):
    
        low, high=0, len(nums)-1
        while low<high:
            mid=low+(high -low)//2
            if nums[mid] < target:
                low=mid+1
            else:
                high=mid
        return high
    
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        count = 0
        for age in ages:
            
            left= self.B_search(ages,  int((0.5 * age) + 7)+1)
            right= self.B_search(ages,age+1)
            if right==len(ages)-1 and ages[right]==age:
                right+=1
            
            if ages[left]==(0.5 * age) + 7:
                left+=1
            count += max(0, right - left - 1)                
        return count

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        ans = 0
        l, r, N = 0, 0, len(ages)
        same_count = 0
        while r < N:
            same_count = 1
            while r+1 < N and ages[r+1] == ages[r]:
                same_count += 1
                r += 1
            while l < r and ages[l] <= 0.5*ages[r]+7:
                l += 1
            if l != r:
                ans += same_count*(r-l)
            r += 1
        return ans


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        n = len(ages)
        if n < 2: return 0
        
        ages.sort()
        
        mins = [0] * n
        pairs = [0] * n
        
        mins[0] = ages[0] / 2 + 7
        
        for i in range(1, n):
            mins[i] = (ages[i] - ages[i-1]) / 2 + mins[i-1]
            
            if ages[i-1] <= mins[i]:
                continue
            
            if mins[i] == mins[i-1]:
                pairs[i] = pairs[i-1] + 2
                continue

            j = i - 1
            while j >= 0 and ages[j] > mins[i]:
                pairs[i] += 1
                if ages[j] == ages[i]: pairs[i] += 1
                j-=1

        return sum(pairs)

from collections import Counter
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        dic = Counter(ages)
        res = 0
        for ageA, cntA in list(dic.items()):
            for ageB, cntB in list(dic.items()):
                if (ageB <= 0.5*ageA + 7) or (ageB > ageA) or (ageB > 100 and ageA < 100):
                    continue
                    
                res += cntA*cntB
                
                if ageA == ageB:
                    res -= cntA
                    
        return res


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        '''
        Algorithm
        ---------
        We first count the frequency of the ages
        '''
        def friendRequests(age_a, age_b):
            if age_b <= (0.5 * age_a + 7) or age_b > age_a:
                return False
            return True
        age_groups = collections.Counter(ages)
        total_requests = 0
        
        for age_a, count_a in list(age_groups.items()):
            for age_b, count_b in list(age_groups.items()):
                if friendRequests(age_a,age_b):
                    total_requests += count_a * count_b
                    
                    # if both candidates are the same, we reduce total
                    # requests by one of their frequencies
                    if age_a == age_b:
                        total_requests -= count_a
        return total_requests
            


import collections

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_count = collections.Counter(ages)
        res = 0
        for age_A, count_A in age_count.items():
            for age_B, count_B in age_count.items():
                if not age_B <= age_A * 0.5 + 7 and not age_B > age_A:
                    res += count_A * count_B
                    if age_A == age_B:
                        res -= count_A
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        c = collections.Counter(ages)
        count = 0
        
        for a in c:
            for b in c:
                if self.request(a, b):
                    continue
                count += c[a]*c[b]
                
                if a == b:
                    count -= c[a]
                    
        return count

    def request(self, a, b):
        return (b<=0.5*a+7 or b > a or a < 100 < b)

#         c = collections.Counter(ages)
#         count = 0
        
#         for a in c:
#             for b in c:
#                 result = self.request(a, b)
#                 if result:
#                     continue
                
#                 count += c[a] * c[b]
#                 if a == b:
#                     count -= c[b]
#         return count


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counts = [0]*121
        for age in ages:
            counts[age] += 1
        SUM = 0
        sums = []
        for c in counts:
            SUM += c
            sums.append(SUM)
        res = 0
        for age in range(15 ,121):
            up = age
            down = age//2 + 7
            res += counts[age] * (sums[up]-sums[down]-1) 
        return res
        
         


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        c = collections.Counter(ages)
        def request(x, y):
            return not (y <= 0.5 * x + 7 or (x < 100 and y > 100) or x < y)
        
        ans = 0
        for x in c:
            for y in c:
                if request(x, y):
                    if x == y:
                        ans += c[x] * (c[y] - 1)
                    else:
                        ans += c[x] * c[y]
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        c = collections.Counter(ages)
        count = 0
        
        for a in c:
            for b in c:
                result = self.request(a, b)
                if result:
                    continue
                
                count += c[a] * c[b]
                if a == b:
                    count -= c[b]
        return count

    def request(self, a, b):
        return (b<=0.5*a+7 or b > a or a < 100 < b)
    
    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort(reverse = True)
        n = len(ages)
        def check(a,b):
            if b <= (a*0.5)+7:
                return False
            if b> a:
                return False
            if b> 100 and a< 100:
                return False
            return True
        res = 0
        c = collections.Counter(ages)
        for a in c:
            for b in c:
                if check(a,b):
                    res+= c[a]*(c[b]-(a==b))
        return res


class Solution:
    def numFriendRequests(self, ages) -> int:
        ages = collections.Counter(ages)
        ans = 0
        for ageA, countA in list(ages.items()):
            for ageB, countB in list(ages.items()):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA
        return ans


import collections
class Solution:
    
    #problem: https://leetcode.com/problems/friends-of-appropriate-ages/
    # refered the solution in : https://leetcode.com/problems/friends-of-appropriate-ages/discuss/737217/Python-simple-solution-using-counters-beats-85
    
    
    def numFriendRequests(self, ages: List[int]) -> int:
        
        count = 0 # the number of friend requests
        
        table = collections.Counter(ages)
        
        for ageA in table:
            num_ = table[ageA] # the number age' people
            for ageB in table:
                if ageB <= 0.5 * ageA + 7:
                    continue
                if ageB > ageA:
                    continue
                if ageB > 100 and ageA < 100:
                    continue
                # if the age is not me
                if ageA != ageB:
                    count += num_ * table[ageB]
                else:
                    count += int(num_ * (num_ - 1))
                    
        return count
                    
        


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def helper(a,b):
            tmpB = a*0.5+7
            return 0 if b<=tmpB or b>a or (b>100 and a<100) else 1
        res,n = 0,len(ages)
        if n == 1:
            return res
        counts = Counter(ages)
        for ageA in counts:
            for ageB in counts:
                countA,countB = counts[ageA],counts[ageB]
                if helper(ageA,ageB):
                    res += countA*countB
                    if ageA == ageB:
                        res -= countA
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = 0
        
        counter = [0]*121
        for i in ages:
            counter[i] += 1
        
        for a in range(1, 121):
            for b in range(1, 121):
                if b > a:
                    continue
                
                if b <= 0.5*a+7:
                    continue
                
                if b > 100 and a < 100:
                    continue
                
                count += counter[a]*counter[b]
                
                if a == b:
                    count -= counter[a]
        
        return count

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def cond(a, b):
            return not (b <= 0.5 * a + 7 or b>a or (b > 100 and a < 100))

        freq = Counter(ages).items()
        cnt= 0
        for a, r in freq:
            for b, c in freq:                
                if cond(a,b):
                    if a==b: cnt+=(r*(r-1))
                    else: cnt+=r*c
        return cnt

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counter = [0]*121
        res = 0
        for a in ages:
            if a<=14: continue
            counter[a] += 1
            
        for i in range(15, 121):
            for j in range(i+1):
                if j<=0.5*i+7: continue
                res += counter[i]*counter[j]
                
                if i==j:
                    res -= counter[i]
                    
        return res

import math

from collections import Counter
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        sol = 0
        c = Counter(ages)
        smaller_equal_age = [0]
        for i in range(1,121):
            smaller_equal_age.append(smaller_equal_age[-1] + c[i])
        for i in range(15,121):
            sol += c[i] * (smaller_equal_age[i] - 1 - smaller_equal_age[math.floor(0.5 * i + 7)])
        return sol

class Solution:
    def numFriendRequests(self, ages) -> int:
        ages = Counter(ages)
        ans = 0
        for age_a, count_a in ages.items():
            for age_b, count_b in ages.items():
                if age_a * 0.5 + 7 >= age_b:
                    continue
                if age_a < age_b:
                    continue
                if age_a < 100 and age_b > 100:
                    continue
                ans += count_a * count_b
                if age_a == age_b:
                    ans -= count_a
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for a in ages:
            count[a] += 1
        # * iterates entire count
        for i, val in enumerate(count):
            count[i] = count[i - 1] + val

        total = 0
        for a in ages:
            ageMin = floor(0.5 * a + 8)
            ageMax = min(a, 120)
            ageMin = max(ageMin - 1, 0)
            total += max(count[ageMax] - count[ageMin] - 1, 0)
            # * total += max(count[min(ageMax, 120)] - count[max(ageMin - 1, 0)] - 1, 0)

        return total


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def request(a, b):
            return not (b <= 0.5 * a + 7 or b > a or b > 100 and a < 100)
        c = collections.Counter(ages)
        return sum(request(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c)

from collections import Counter
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        c = Counter(ages)
        return sum(self.can_be_friend(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c)
        
    
    
    def can_be_friend(self, age1, age2):
        if age2 <= 0.5 * age1 + 7 or age2 > age1 or (age2 > 100 and age1 < 100):
            return False
        return True

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        nums=[0]*121
        for age in ages:
            nums[age]+=1
        ans=0
        request=[set() for i in range(121)]
        for i in range(1,121):
            for j in range(1,121):
                if (not ((j<=i//2+7) or (j>i) or (j>100 and i<100))):
                    request[i].add(j)
        for i in range(1,121):
            for j in request[i]:
                ans+=nums[i]*(nums[j] if i!=j else(nums[j]-1))
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        '''
        102
        
        A -- not -> B
        
        B <= 0.5A + 7
        B > A
        ~ B > 100 & A < 100
        
        split to > 100, < 100 groups
        
        
        right to left, > 100 region
        
        '''

        count = [0] * 121
        for age in ages:
            count[age] += 1
        
        res = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                
                if (ageA * 0.5 + 7 >= ageB): continue
                if (ageA < ageB): continue
                if (ageA<100 and ageB >100): continue
                
                res += countA * countB
                if ageA == ageB: 
                    res -= countA
        return res
                    


'''class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        total_age = 121
        ageCnt = [0]*total_age
        prefixSum = [0]*total_age
        for age in ages:
            ageCnt[age] += 1
        for i in range(1, total_age):
            prefixSum[i] = ageCnt[i] + prefixSum[i-1]
        res = 0 
        for i in range(15, total_age):
            if ageCnt[i] == 0:
                continue 
            res += ageCnt[i]*(prefixSum[i]-prefixSum[int(i*.5+7)]-1)#)- ageCnt[i]
        return res '''

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        maxAge = 121 
        preSum = [0]*maxAge 
        from collections import Counter 
        ageCnt = Counter(ages)
        for i in range(1, maxAge):
            preSum[i] += preSum[i-1] + ageCnt[i]
        res =0 
        for age in range(15, maxAge):
            res += (preSum[age]-preSum[int(.5*age+7)]-1) * ageCnt[age]
        return res 
            
        
        
        '''
        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
        '''
        '''from collections import Counter 
        cnt = Counter(ages)
        res = 0 
        def request(a,b):
            return not (b <= .5*a+7 or b>a)
        for a in cnt:
            for b in cnt:
                res += request(a,b)*cnt[a]*(cnt[b]-(a==b))
        return res '''
            
        
        
        
        


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        valid_ages = [0] * 121
        for age in ages:
            valid_ages[age] += 1
        
        count = 0
        for i in range(1, 121):
            ageA = valid_ages[i]
            for j in range(1, 121):
                ageB = valid_ages[j]
                if j <= 0.5 * i + 7 or j > i:
                    continue
                if j > 100 and i < 100:
                    continue 
                count += ageA * ageB
                if i == j:
                    count -= ageA
        return count

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        # first start something simple 
        # should be able to do this in O(n) 
        ages.sort()
        ans, i, j = 0, 0, 0
        while i < len(ages): 
            val = ages[i]
            while j < i and ages[j] <= (0.5 * val + 7): 
                j += 1
            cnt, num_equal = i - j, 0
            while i < len(ages) and ages[i] == val: 
                num_equal, i = num_equal + 1, i+1
            # here could be either out of bound of different value
            ans += (num_equal * cnt) + (num_equal * (num_equal-1))
        return ans
    def numFriendRequests(self, ages):
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                # if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:       
        age_counts = [0] * 121
        for age in ages:
            age_counts[age] += 1
            
        request_count = 0
        for ageA, age_countA in enumerate(age_counts):
            for ageB, age_countB in enumerate(age_counts):    
                if ageB <= ((.5 * ageA) + 7):
                    continue
                if ageB > ageA:
                    continue
                if ageA < 100 < ageB:
                    continue
                request_count += age_countA * age_countB
                
                if ageA == ageB:
                    request_count -= age_countA
        
        return request_count

class Solution:
    def numFriendRequests(self, ages):
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for age in ages:
            count[age] += 1
        res = 0 
        for age_a, count_a in enumerate(count):
            for age_b, count_b in enumerate(count):
                if age_b <= 0.5 * age_a + 7:
                    continue 
                if age_b > age_a:
                    continue 
                if age_b > 100 and age_a < 100:
                    continue 
                res += count_a * count_b
                if age_a == age_b:
                    res -= count_a
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        max_age = 0
        for age in ages:
            count[age] += 1
            max_age = max(max_age, age)
            
        ans = 0
        for ageA, countA in enumerate(count[:max_age+2]):
            for ageB, countB in enumerate(count[:max_age+2]):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans   

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for age in ages:
            count[age] += 1
        
        res = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageB <= ageA*0.5+7: continue
                if ageB > ageA: continue
                if ageB > 100 and ageA < 100: continue
                res += countA*countB
                if ageA == ageB: res-=countA
        
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans


'''
不考虑遍历所有的 20000 个人，我们只考虑遍历所有的元组 (age, count) 表示在这个年纪有多少人。因为最多只有 120 个可能的年纪，这会是一个很快的提升。

算法

对于每个元组 (ageA, countA)，(ageB, countB)，如果条件满足对应的年纪，那么久将 countA * countB 加入发好友请求的人数。

当 ageA == ageB 的时候我们就数多了：我们只有 countA * (countA - 1) 对好友请求，因为你不能和自己发送请求。

JavaPython



'''

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        requests = 0
        ageCount = [0] * 121
        for age in ages:
            ageCount[age] += 1

        for A in range(120, 14, -1):
            if not ageCount[A]:
                continue
            requests += (ageCount[A] * (ageCount[A] - 1))
            for B in range(A-1, int(0.5*A + 7), -1):
                requests += (ageCount[A] * ageCount[B])
        return requests

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        a = sorted(ages)
        i,j,k = 0,0,0
        ans = 0
        for i in range(1,len(a)):
            if a[i] <= 14: continue
            lb = a[i]*0.5 + 7
            while a[j] <= lb:
                j += 1
            ans += i-j
            if a[k] != a[i]:
                k = i
            ans += i-k
        return ans


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_dict = collections.Counter(ages)
        sorted_ages = sorted(age_dict.keys())
        requests = 0
        for i in sorted_ages:
            for j in sorted_ages:
                if (j>100 and i<100) or (j<=0.5*i+7): continue
                if j>i: break
                if i==j: requests += age_dict[i]*(age_dict[j]-1)
                else: requests +=age_dict[i]*age_dict[j]
        return requests
            


'''
PASS
[1, 2, 32, 32, 40, 41, 50]
[1, 2, 50]
[1, 2, 40, 41, 50] 
[40, 41, 50]
[16,16]
[6, 6]
'''

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        '''
        Observation: ages might be long (20,000), but there are only 120
        possible values for ages.
        '''
        
        ageCounts = Counter(ages)
        numRequests = 0
        
        '''
        [8,85,24,85,69]
        '''
        
        for a in range(1, 121):                
            if ageCounts[a] > 0:
                exclLowerBound = 0.5*a + 7
                lowerBound = ceil(exclLowerBound)
            
                if lowerBound == exclLowerBound:
                    lowerBound += 1
                    
                for a2 in range(lowerBound, a):
                    # multiply by ageCounts[a], each instance will send FR
                    numRequests += ageCounts[a2]*ageCounts[a]
                    
                if lowerBound <= a: # 16, 16, 16
                    # each instance will send FR to all the others
                    numRequests += ageCounts[a]*(ageCounts[a] - 1)
            
        return numRequests


class Solution:
    def check(self, a, b):
        if b <= 0.5*a+7:
            return False
        if b > a:
            return False
        if b > 100 and a < 100:
            return False
        
        return True
    
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = 0
        c = [0 for x in range(121)]
        
        for a in ages:
            c[a] += 1
        
        #print(c)
        
        for i in range(len(c)):
            for j in range(len(c)):
                if self.check(i, j):
                    #print(i, j)
                    #print(ages[i], ages[j])
                    cnt += c[i]*c[j]
                    if i == j:
                        cnt -= c[i]
                    
        return cnt

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        dp=[0]*(121)
        for i in ages:
            dp[i]+=1
        
        ans=0
        mp={}
        for i in range(15,121):
            p=0
            if dp[i]>0:
                if i%2==0:
                    Min=int((i/2)+8)
                else:
                    Min=int(math.ceil((i/2)+7))
                # Min=int(0.5*i+7)
                Max=i
                j=Min
                while j<=Max and j<=120:
                    if j==i:
                        ans+=dp[j]*(dp[j]-1)
                        p+=dp[j]*(dp[j]-1)
                    else:
                        ans+=dp[i]*dp[j]
                        p+=dp[i]*dp[j]
                    j+=1

                mp[i]=p
        
        # print(mp)
        return ans


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counts = Counter(ages)
        requests = 0
        
        conditions = [
            lambda ageA, ageB: 0.5 * ageA + 7 >= ageB,
            lambda ageA, ageB: ageA < ageB
        ]
        
        def canSendRequest(ageA, ageB):
            return not any(condition(ageA, ageB) for condition in conditions)
        
        for ageA, countA in counts.items():
            for ageB, countB in counts.items():
                if canSendRequest(ageA, ageB):
                    if ageA == ageB:
                        requests += countA * (countA - 1)
                    else:
                        requests += countA * countB
        
        return requests

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counts = Counter(ages)
        requests = 0
        
        conditions = [
            lambda ageA, ageB: 0.5 * ageA + 7 >= ageB,
            lambda ageA, ageB: ageA < ageB            
        ]
        
        def canSendRequest(ageA, ageB):
            # if any condition is True, then we can't request friend             
            return not any(condition(ageA, ageB) for condition in conditions)   
         
        for ageA, countA in counts.items():
            for ageB, countB in counts.items():
                if canSendRequest(ageA, ageB):
                    
                    if ageA == ageB:
                        requests += countA * (countA - 1)
                    else:
                        requests += countA * countB
                
        return requests

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counts = Counter(ages)
        requests = 0
        
        conditions = [
            lambda ageA, ageB: 0.5 * ageA + 7 >= ageB,
            lambda ageA, ageB: ageA < ageB
        ]
        
        def canRequestFriend(ageA, ageB):
            return not any(condition(ageA, ageB) for condition in conditions)
        
        for ageA, countA in list(counts.items()):
            for ageB, countB in list(counts.items()):
                if canRequestFriend(ageA, ageB):
                    if ageA == ageB:
                        requests += countA * (countA - 1)
                    else:
                        requests += countA * countB
                
        return requests


class Solution:
    
    #problem: https://leetcode.com/problems/friends-of-appropriate-ages/
    # refered the solution in : https://leetcode.com/problems/friends-of-appropriate-ages/discuss/837786/Binary-Search-beating-100-with-detail-explanation
    
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        right_most = {}
        for ix,x in enumerate(ages):
            right_most[x] = ix
        
        l = 0
        count = 0
        for ix,x in enumerate(ages):
            while ages[l]<= (x/2 + 7) and l<right_most[x]:
                l+=1
            count+= right_most[x] - l
        return count


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = collections.Counter(ages)
        
        #print(count)
        ans = 0
        
        for ageA in count:
            for ageB in count:
                countA = count[ageA]
                countB = count[ageB]
                if ageB <= ageA*0.5 + 7:
                    continue
                if ageA < ageB:
                    continue
                ans += countA * countB
                if ageA == ageB:
                    ans -= countA
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_count = Counter(ages)
        distinct_ages = set(age_count.keys())
        total_req = 0
        
        for a_age in distinct_ages:
            a_frn_req = 0
            for b_age in distinct_ages:
                if b_age > a_age or (a_age < 100 < b_age) or b_age <= (0.5 * a_age + 7):
                    continue

                a_frn_req += age_count[a_age] * age_count[b_age]
                if a_age == b_age: a_frn_req -= age_count[a_age]
                
            total_req += a_frn_req
            
        return total_req

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counts = collections.Counter(ages)
        valid = lambda A, B: not any([A *.5 + 7 >= B, A < B, A < 100 < B])
        count = 0
        
        items = list(counts.items())
        for A, cntA in items:
            for B, cntB in items:
                if valid(A, B):
                    count += cntA * cntB
                    if A == B:
                        count -= cntA
        
        return count
            
            
        


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_count = [0] * 121
        for age in ages:
            age_count[age] += 1
            
        res = 0
        print(len(age_count))
        for i in range(121):
            for j in range(121):
                if  age_count[i] > 0 and age_count[j] > 0:
                    if j <= 0.5 * i + 7 or j > i:
                        continue
                    res += age_count[i] * age_count[j]
                    if i == j:
                        res -= age_count[i] # One doesn't send request to himself
                        
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for age in ages:
            count[age] += 1
        answer = 0
        for age_a, count_a in enumerate(count):
            for age_b, count_b in enumerate(count):
                if age_a * 0.5 + 7 >= age_b:
                    continue
                if age_a < age_b:
                    continue
                if age_a < 100 < age_b:
                    continue
                
                answer += count_a * count_b
                
                if age_a == age_b:
                    answer -= count_a
                    
        return answer
                    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        agesCount = [0]*121
        for age in ages:
            agesCount[age] += 1
        
        res = 0
        for i in range(1, 121):
            for j in range(1, 121):
                if agesCount[i] == 0 or agesCount[j] == 0 or j > i or (j > 100 and i < 100) or (j <= i/2 + 7):
                    continue
                
                res += agesCount[i]*agesCount[j]
                if i == j:
                    res -= agesCount[i]  #because I can't send request to myself
        
        return res

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = collections.Counter(ages)
        
        print(count)
        ans = 0
        
        for ageA in count:
            for ageB in count:
                countA = count[ageA]
                countB = count[ageB]
                if ageB <= ageA*0.5 + 7:
                    continue
                if ageA < ageB:
                    continue
                ans += countA * countB
                if ageA == ageB:
                    ans -= countA
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_library = {}

        for age in ages:
            age_library[age] = age_library.get(age, 0) + 1

        res = 0
        for A, numA in list(age_library.items()):
            for B, numB in list(age_library.items()):
                if not (B <=0.5*A + 7 or B > A or (B > 100 and A < 100)):
                    res += numA * numB - numA*(A == B)
        return res


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        def request(a, b):
            return not (b <= 0.5 * a + 7 or b > a or b > 100 and a < 100)
        c = collections.Counter(ages)
        return sum(request(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c)


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = collections.Counter(ages)
        
        res = 0
        for p1 in cnt:
            for p2 in cnt:
                # print(cnt, p1, p2, res)
                if p2 <= 0.5 * p1 + 7 or p2 > p1 or (p2 > 100 and p1 < 100):
                    continue
                if p1 == p2:
                    res += (cnt[p1]-1)*cnt[p1]
                else:
                    res += cnt[p1] * cnt[p2]

        return res


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        if not ages:
            return 0
        agesToCount = [0] * 121
        for age in ages:
            agesToCount[age] += 1

        result = 0
        for ageA in range(1, 121):
            for ageB in range(1, 121):
                if ageB <= ageA and ageB > 0.5 * ageA + 7:
                    if ageA == ageB:
                        result += agesToCount[ageA] * (agesToCount[ageA] - 1)
                    else:
                        result += agesToCount[ageA] * agesToCount[ageB]
        return result

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        buckets = [0] * 121
        for age in ages:
            buckets[age] += 1
        
        ans = 0
        for i in range(1, 121):
            if buckets[i] <= 0:
                continue
            for j in range(1, 121):
                if buckets[j] <= 0:
                    continue
                
                if j <= 0.5 * i + 7 or j > i or (j > 100 and i < 100):
                    continue
                
                ans += buckets[i] * buckets[j]
                if i == j:
                    ans -= buckets[i]
        
        return ans

'''

Arr: [16, 16]


Arr: [16, 16, 17, 18]


{16:2, 17: 1, 18:1}

A: 16, B = 17

17 <= 8 + 7

17 <= 15 NOT


{16:2, 17: 1, 18:1}

{16:2, 17: 1, 18:1}

2 + 2 + 0 + 1

[20,30,100,110,120]

{20:1, 30:1, 100:1, 110:1, 120: 1}

{20:1, 30:1, 100:1, 110:1, 120: 1}

20:0
30:1, 30: B, 20: A  30 <= 17
100:0

Solution:

Count the ages. 

* For each age, compare with other ages and figure how many possible matches happen. 
'''
from collections import Counter

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        # if there are no ages
        if not ages:
            return 0
        
        def friend (A, B):
            if B > A:
                return False
            if B <= (A * 0.5) + 7:
                return False
            return True
        
        # define a counter for ages
        counter = Counter (ages)
        
        # total friend requests
        requests = 0
        
        # iterate over the ages
        # [16, 16, 16] => 2, 2, 2 => 6
        for ageA, countA in list(counter.items()):
            for ageB, countB in list(counter.items()):
                if friend(ageA, ageB):
                    requests = requests + (countA * countB) if ageA != ageB else requests + (countA - 1) * countA
                    
        return requests


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        count = Counter(ages)
        ans= 0
        for i in count:
            for j in count:
                if not (j <= i * 0.5 + 7 or j > i):
                    ans+=count[i]*count[j]
                    if j==i:
                        ans-=count[i]
        return ans


class Solution(object):
    def numFriendRequests(self, ages):
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                
                if ageA == ageB: ans -= countA

        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        count = collections.Counter(ages)
        
        ans = 0
        for A, countA in count.items():
            for B, countB in count.items():
                if B <= 0.5 * A + 7: continue
                elif B > A: continue
                elif B > 100 and A < 100: continue
                    
                ans += countA * countB
                if A == B:
                    ans -= countA
        
        return ans

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        age_cnt = [0] * 121
        for age in ages:
            age_cnt[age] += 1
        
        res = 0
        for ageA, cntA in enumerate(age_cnt):
            for ageB, cntB in enumerate(age_cnt):
                if ageB <= (0.5 * ageA + 7) or ageB > ageA or (ageB > 100 and ageA < 100):
                    continue
                res += (cntA * cntB)
                if ageA == ageB:
                    res -= cntA
        return res

class Solution:
    '''
    a will quest b if
        b > 0.5 * a + 7
        b <= a
        b and a both < or > 100, or a or b is 100
    bucket sort!
    
    ''' 
    def numFriendRequests(self, ages: List[int]) -> int:
        ct = Counter(ages)
    
        res = 0
        for a in ct:
            for b in ct:
                if b <= 0.5 * a +7: continue
                if b > a: continue
                #if b > 100 and a < 100: continue
                res += ct[a] * ct[b] if a!= b else ct[a]**2 - ct[a]
        return res


class Solution:
    def numFriendRequests(self, ages):
        def request(a, b):
            return not (b <= 0.5 * a + 7 or b > a or b > 100 and a < 100)
        c = collections.Counter(ages)
        return sum(request(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c)

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        c = collections.Counter(ages)
        return sum(self.sendFriend(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c)
        
    
    def sendFriend(self,A,B):
        if B <= 0.5*A+7:
            return False
        if B > A:
            return False
        if B >100 and A<100:
            return False
        return True
        


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        d={}
        ans=0
        
        for age in ages:
            if(age not in d):
                d[age]=1
            else:
                d[age]+=1
        
        print (d)
        for ageA,countA in (list(d.items())):
            for ageB ,countB in (list(d.items())):
                print((ageA,countA,ageB,countB))
                
                if(ageA*0.5+7>=ageB):
                    continue
                    
                if(ageA<ageB):
                    continue
                    
                if(ageA<100<ageB):
                    continue
                    
                if(ageA!=ageB):
                    ans+=countA*countB
                else:
                    ans+=(countA-1)*countA
                # if(ageA==ageB):
                #     ans-=countA
        return ans
                    


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        
        count = [0]*121
        for age in ages:
            count[age] += 1
        
        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB:
                    continue
                if ageA < ageB:
                    continue
                if ageA < 100 < ageB:
                    continue
                ans += countA * countB
                if ageA == ageB:
                    ans -= countA
        return ans


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        right_most = {}
        for ix,x in enumerate(ages):
            right_most[x] = ix
        
        l = 0
        count = 0
        for ix,x in enumerate(ages):
            while ages[l]<= (x/2 + 7) and l<right_most[x]:
                l+=1
            count+= right_most[x] - l
        return count

import bisect
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        if not ages: 
            return 0
        cnt = 0
        N = len(ages)
        ages.sort()
        for i in range(N):
            a = ages[i]
            if a<=14: #含14歲以前不能交朋友 => 數學推導
                continue
            idx1 = bisect.bisect(ages, a)
            x = 0.5*a+7
            idx2 = bisect.bisect(ages, x)
            while idx2<N and ages[idx2]==x: #找出右boundary
                idx2 += 1
            cnt += max(0, idx1-idx2+(-1 if idx2<=i<=idx1 else 0)) #不能跟自己交朋友
        return cnt
                
        


class Solution:
    
    #problem: https://leetcode.com/problems/friends-of-appropriate-ages/
    
    def numFriendRequests(self, ages: List[int]) -> int:
        count = [0] * 121
        for age in ages:
            count[age] += 1

        ans = 0
        for ageA, countA in enumerate(count):
            for ageB, countB in enumerate(count):
                if ageA * 0.5 + 7 >= ageB: continue
                if ageA < ageB: continue
                if ageA < 100 < ageB: continue
                ans += countA * countB
                if ageA == ageB: ans -= countA

        return ans