{x}
blog image

Friends Of Appropriate Ages

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

Solution Explanation: Friends of Appropriate Ages

This problem involves determining the total number of friend requests that can be made among a group of people based on their ages and specific criteria. The solution presented uses a counting approach for efficiency.

Approach:

  1. Counting Ages: We first create a frequency array cnt (or similar data structure depending on the language) of size 121 (since ages range from 1 to 120). This array stores the count of people for each age. We iterate through the input ages array, incrementing the count for each age in cnt. This step takes O(n) time, where n is the length of the ages array.

  2. Iterating Age Pairs: We then iterate through all possible pairs of ages (ax, ay) from 1 to 120. For each pair, we check if a friend request is allowed according to the given rules:

    • ay <= 0.5 * ax + 7: The younger person's age (ay) is less than or equal to half the older person's age (ax) plus 7.
    • ay > ax: The younger person's age is greater than the older person's age.
    • ay > 100 && ax < 100: The younger person is over 100, and the older person is under 100.

    If none of these conditions are true, a friend request is allowed.

  3. Calculating Friend Requests: If a friend request is allowed, we add to the total count (ans) the number of possible friend requests between people of ages ax and ay.

    • If ax == ay (same age), the number of requests is cnt[ax] * (cnt[ax] - 1) (each person requests everyone else of the same age).
    • If ax != ay, the number of requests is cnt[ax] * cnt[ay] (each person of age ax requests every person of age ay).

  4. Returning the Result: Finally, the function returns the total number of friend requests (ans).

Time Complexity:

The dominant factor in the time complexity is the nested loop iterating through all possible age pairs (from 1 to 120). This results in O(m^2) time complexity, where m is the maximum age (120 in this case). The initial counting step takes O(n) time. Therefore, the overall time complexity is O(n + m^2). Since m is a constant (120), we can also consider this approximately O(n) when n is large enough.

Space Complexity:

The space complexity is O(m) due to the cnt array used to store the age counts. Again, m is a constant (120), so this is effectively O(1) constant space complexity.

Code Examples (Already provided in the original response): The original response includes well-structured code examples in Python, Java, C++, Go, and TypeScript, demonstrating the solution described above. Each example efficiently implements the counting and iteration steps, adhering to the specified time and space complexities.