Friends Of Appropriate Ages

Medium
1126.

Friends Of Appropriate Ages

Friends Of Appropriate Ages is a medium coding problem on arrays, sorting and counting, asked in Amazon and Meta interviews.

A community has n members and ages[i] is the age of member i.

Member x sends a friend request to member y (with x != y) unless at least one of these holds:

  • ages[y] <= 0.5 * ages[x] + 7
  • ages[y] > ages[x]
  • ages[y] > 100 and ages[x] < 100

Requests are one-way: x requesting y does not imply y requests x, and nobody requests themselves. Return the total number of friend requests sent.

Example 1

Input
ages = [17,18,19]
Output
3
Explanation
18 requests 17, and 19 requests both 18 and 17.

Example 2

Input
ages = [14,14]
Output
0
Explanation
`14 <= 0.5 * 14 + 7`, so neither sends a request.

Example 3

Input
ages = [25,60,61,99]
Output
3
Explanation
61 requests 60, and 99 requests 61 and 60.

Constraints

  • n == ages.length
  • 1 <= n <= 2 * 10^4
  • 1 <= ages[i] <= 120
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} ages
 * @return {number}
 */
var numFriendRequests = function(ages) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Friends Of Appropriate Ages — Solution in Python, Java & C++

Friends Of Appropriate Ages solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Friends Of Appropriate Ages is a medium coding problem on arrays, sorting and counting, asked in Amazon and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Counting
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A community has n members and ages[i] is the age of member i.

Member x sends a friend request to member y (with x != y) unless at least one of these holds:

  • ages[y] <= 0.5 * ages[x] + 7
  • ages[y] > ages[x]
  • ages[y] > 100 and ages[x] < 100

Requests are one-way: x requesting y does not imply y requests x, and nobody requests themselves. Return the total number of friend requests sent.

Example 1

Input: ages = [17,18,19]
Output: 3
Explanation: 18 requests 17, and 19 requests both 18 and 17.

Example 2

Input: ages = [14,14]
Output: 0
Explanation: `14 <= 0.5 * 14 + 7`, so neither sends a request.

Example 3

Input: ages = [25,60,61,99]
Output: 3
Explanation: 61 requests 60, and 99 requests 61 and 60.

Constraints

  • n == ages.length
  • 1 <= n <= 2 * 10^4
  • 1 <= ages[i] <= 120

Hints for Friends Of Appropriate Ages

  1. Hint 1

    Comparing every pair of people is O(n^2), but there are only 120 possible ages.

  2. Hint 2

    Count how many people have each age, then reason about pairs of ages instead of pairs of people.

  3. Hint 3

    For ages a and b, if a may request b, that contributes count[a] * count[b] requests — minus count[a] when a == b, since nobody requests themselves.

How to solve Friends Of Appropriate Ages

The rule depends only on the two ages, so group people by age and count requests between age buckets.

Approach

  1. Build count[age] for ages 1..120.
  2. For every pair of ages (a, b) with b <= a and 2 * b > a + 14 (the integer form of b > 0.5a + 7), add count[a] * count[b].
  3. When a == b, use count[a] - 1 instead of count[b] so a person never requests themselves.
  4. Return the total.

Why it works

Two people of the same ages behave identically under the rules, so the number of requests from bucket a to bucket b is the product of their sizes (excluding self-pairs when the buckets coincide). The third rule never adds a restriction: if b > 100 and a < 100, then b > a already rejects the pair.

Complexity

  • Time — O(n + 120^2)
  • Space — O(120)

Pitfalls

  • Forgetting to subtract self-requests inside the same age bucket.
  • Using floating point for 0.5 * a + 7 invites rounding mistakes; compare 2 * b <= a + 14 instead.
  • Anyone aged 14 or less never sends a request at all, since b <= a forces 2b <= a + 14.

Reference solution

Python

from typing import List

def numFriendRequests(ages: List[int]) -> int:
    count = [0] * 121
    for a in ages:
        count[a] += 1
    total = 0
    for a in range(1, 121):
        if count[a] == 0:
            continue
        for b in range(1, a + 1):
            if count[b] == 0 or 2 * b <= a + 14:
                continue
            total += count[a] * (count[b] - (1 if a == b else 0))
    return total

Java

public static int numFriendRequests(int[] ages) {
    int[] count = new int[121];
    for (int a : ages) count[a]++;
    int total = 0;
    for (int a = 1; a <= 120; a++) {
        if (count[a] == 0) continue;
        for (int b = 1; b <= a; b++) {
            if (count[b] == 0 || 2 * b <= a + 14) continue;
            total += count[a] * (count[b] - (a == b ? 1 : 0));
        }
    }
    return total;
}

C++

int numFriendRequests(vector<int>& ages) {
    vector<int> count(121, 0);
    for (int a : ages) count[a]++;
    int total = 0;
    for (int a = 1; a <= 120; a++) {
        if (count[a] == 0) continue;
        for (int b = 1; b <= a; b++) {
            if (count[b] == 0 || 2 * b <= a + 14) continue;
            total += count[a] * (count[b] - (a == b ? 1 : 0));
        }
    }
    return total;
}

JavaScript

var numFriendRequests = function(ages) {
    var count = new Array(121).fill(0);
    for (var i = 0; i < ages.length; i++) count[ages[i]]++;
    var total = 0;
    for (var a = 1; a <= 120; a++) {
        if (count[a] === 0) continue;
        for (var b = 1; b <= a; b++) {
            if (count[b] === 0 || 2 * b <= a + 14) continue;
            total += count[a] * (count[b] - (a === b ? 1 : 0));
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms