Skip to content

825. Friends Of Appropriate Ages

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 \(\textit{cnt}\) of length \(121\) to record the number of people of each age.

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

If \(\textit{ax} = \textit{ay}\), meaning the ages are the same, then the number of friend requests between \(\textit{ax}\) and \(\textit{ay}\) is \(\textit{cnt}[\textit{ax}] \times (\textit{cnt}[\textit{ax}] - 1)\). Otherwise, if the ages are different, the number of friend requests between \(\textit{ax}\) and \(\textit{ay}\) is \(\textit{cnt}[\textit{ax}] \times \textit{cnt}[\textit{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 \(\textit{ages}\), and \(m\) is the maximum age, which is \(121\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
}

Comments