LeetCode 0825. Friends Of Appropriate Ages Solution in Java, C++, Python & More | Explanation + Code

Description

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

 

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 -> 16, 18 -> 17.

Example 3:

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

 

Constraints:

• n == ages.length
• 1 <= n <= 2 * 104
• 1 <= ages[i] <= 120

Solutions

Solution 1: Counting + Enumeration

We can use an array cnt of length 121 to record the number of people of each age.

Next, we enumerate all possible age pairs (ax, ay). If ax and ay satisfy the conditions given in the problem, these age pairs (ax, ay) can send friend requests to each other.

If ax = ay, meaning the ages are the same, then the number of friend requests between ax and ay is cnt[ax] × (cnt[ax] - 1). Otherwise, if the ages are different, the number of friend requests between ax and ay is cnt[ax] × cnt[ay]. We accumulate these friend request counts into the answer.

The time complexity is O(n + m^2), where n is the length of the array ages, and m is the maximum age, which is 121 in this problem.

PythonJavaC++GoTypeScript

class Solution: def numFriendRequests(self, ages: List[int]) -> int: cnt = [0] * 121 for x in ages: cnt[x] += 1 ans = 0 for ax, x in enumerate(cnt): for ay, y in enumerate(cnt): if not (ay <= 0.5 * ax + 7 or ay > ax or (ay > 100 and ax < 100)): ans += x * (y - int(ax == ay)) return ans(code-box)

class Solution { public int numFriendRequests(int[] ages) { final int m = 121; int[] cnt = new int[m]; for (int x : ages) { ++cnt[x]; } int ans = 0; for (int ax = 1; ax < m; ++ax) { for (int ay = 1; ay < m; ++ay) { if (!(ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100))) { ans += cnt[ax] * (cnt[ay] - (ax == ay ? 1 : 0)); } } } return ans; } }(code-box)

class Solution { public: int numFriendRequests(vector<int>& ages) { const int m = 121; vector<int> cnt(m); for (int x : ages) { ++cnt[x]; } int ans = 0; for (int ax = 1; ax < m; ++ax) { for (int ay = 1; ay < m; ++ay) { if (!(ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100))) { ans += cnt[ax] * (cnt[ay] - (ax == ay ? 1 : 0)); } } } return ans; } };(code-box)

func numFriendRequests(ages []int) (ans int) { cnt := [121]int{} for _, x := range ages { cnt[x]++ } for ax, x := range cnt { for ay, y := range cnt { if ay <= ax/2+7 || ay > ax || (ay > 100 && ax < 100) { continue } if ax == ay { ans += x * (x - 1) } else { ans += x * y } } } return }(code-box)

function numFriendRequests(ages: number[]): number { const m = 121; const cnt = Array(m).fill(0); for (const x of ages) { cnt[x]++; } let ans = 0; for (let ax = 0; ax < m; ax++) { for (let ay = 0; ay < m; ay++) { if (ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100)) { continue; } ans += cnt[ax] * (cnt[ay] - (ax === ay ? 1 : 0)); } } return ans; }(code-box)