Formatted question description: https://leetcode.ca/all/825.html

825. Friends Of Appropriate Ages (Medium)

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 <= 20000.
1 <= ages[i] <= 120.

Companies:
Facebook

Related Topics:
Array

Solution 1.

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        Map<Integer, Integer> ageCountMap = new HashMap<Integer, Integer>();
        for (int age : ages) {
            int count = ageCountMap.getOrDefault(age, 0) + 1;
            ageCountMap.put(age, count);
        }
        int friendRequests = 0;
        int length = ages.length;
        for (int i = 0; i < length; i++) {
            if (i > 0 && ages[i] == ages[i - 1])
                continue;
            int age = ages[i];
            int minAge = age / 2 + 8;
            if (minAge > age)
                continue;
            int minIndex = binarySearch(ages, minAge);
            int count = ageCountMap.get(age);
            friendRequests += count * (i - minIndex);
            friendRequests += count * (count - 1);
        }
        return friendRequests;
    }

    public int binarySearch(int[] ages, int minAge) {
        int low = 0, high = ages.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            int age = ages[mid];
            if (age < minAge)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }
}

############

class Solution {
    public int numFriendRequests(int[] ages) {
        int[] counter = new int[121];
        for (int age : ages) {
            ++counter[age];
        }
        int ans = 0;
        for (int i = 1; i < 121; ++i) {
            int n1 = counter[i];
            for (int j = 1; j < 121; ++j) {
                int n2 = counter[j];
                if (!(j <= 0.5 * i + 7 || j > i || (j > 100 && i < 100))) {
                    ans += n1 * n2;
                    if (i == j) {
                        ans -= n2;
                    }
                }
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/friends-of-appropriate-ages/
// Time: O(N)
// Space: O(1)
class Solution {
private:
    bool request(int A, int B) {
        return !(B <= .5 * A + 7 || B > A);
    }
public:
    int numFriendRequests(vector<int>& ages) {
        int ans = 0;
        vector<int> cnts(120, 0);
        for (int age : ages) cnts[age - 1]++;
        for (int i = 0; i < 120; ++i) {
            if (!cnts[i]) continue;
            for (int j = 0; j < 120; ++j) {
                if (!cnts[j] || !request(i + 1, j + 1)) continue;
                ans += cnts[i] * cnts[j];
                if (i == j) ans -= cnts[i];
            }
        }
        return ans;
    }
};

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

############

class Solution(object):
    def numFriendRequests(self, ages):
        """
        :type ages: List[int]
        :rtype: int
        """
        count = collections.Counter(ages)
        ages = sorted(count.keys())
        N = len(ages)
        res = 0
        for A in ages:
            for B in range(int(0.5 * A) + 7 + 1, A + 1):
                res += count[A] * (count[B] - int(A == B))
        return res

func numFriendRequests(ages []int) int {
	counter := make([]int, 121)
	for _, age := range ages {
		counter[age]++
	}
	ans := 0
	for i := 1; i < 121; i++ {
		n1 := counter[i]
		for j := 1; j < 121; j++ {
			n2 := counter[j]
			if !(j <= i/2+7 || j > i || (j > 100 && i < 100)) {
				ans += n1 * n2
				if i == j {
					ans -= n2
				}
			}
		}
	}
	return ans
}

825 - Friends Of Appropriate Ages

825. Friends Of Appropriate Ages (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

825. Friends Of Appropriate Ages (Medium)

Solution 1.

All Problems

All Solutions