LC 0825 [M] Friends Of Appropriate Ages - ALawliet/algorithms GitHub Wiki

rightmost = bisect = bisect_right

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 (left bound)
age[B] > age[A] (right bound)
age[B] > 100 && age[A] < 100 (redundant)

age[B] = (0.5 * age[A] + 7, age[A])

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ## RC ##
        ## APPROACH  : BINARY SEARCH ##
        ## 1. Sort by age
        ## 2. index i person will not send friend request to ages[i]+1, ages[i]+2 ....
        ## 3. index i person will not send friend request to elements whose age is less than (0.5 * ages[i] + 7)
        ## 4. Using binary search we can find upper and lower limit, persons which fall in this range, can send friend requests (remove 1, ith person itself)
        
        ages.sort()
        count = 0
        for A in range(len(ages)):
            l = bisect(ages, 0.5 * ages[A] + 7)
            r = bisect(ages, ages[A])
            count += max(r - l - 1, 0) # you cannot have negative count
        return count

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

                if ageA == ageB: ans -= countA # undo dupes, only count one-way
                ans += countA * countB
        return ans