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