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] + 7ages[y] > ages[x]ages[y] > 100andages[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.length1 <= n <= 2 * 10^41 <= ages[i] <= 120
Hints for Friends Of Appropriate Ages
Hint 1
Comparing every pair of people is O(n^2), but there are only 120 possible ages.
Hint 2
Count how many people have each age, then reason about pairs of ages instead of pairs of people.
Hint 3
For ages
aandb, ifamay requestb, that contributescount[a] * count[b]requests — minuscount[a]whena == 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
- Build
count[age]for ages 1..120. - For every pair of ages
(a, b)withb <= aand2 * b > a + 14(the integer form ofb > 0.5a + 7), addcount[a] * count[b]. - When
a == b, usecount[a] - 1instead ofcount[b]so a person never requests themselves. - 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 + 7invites rounding mistakes; compare2 * b <= a + 14instead. - Anyone aged 14 or less never sends a request at all, since
b <= aforces2b <= 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 totalJava
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