Friends Of Appropriate Ages - Practice Coding Problems

Friends Of Appropriate Ages - Problem

There are n people on a social media website. You are given an integer array ages where ages[i] is the age of the i^th person.

A person x will not send a friend request to person y (where 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, person x will send a friend request to person 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 themselves.

Return the total number of friend requests made.

Input & Output

Example 1 — Basic Case

$ Input: ages = [16,16]

› Output: 2

💡 Note: Both 16-year-olds can send requests to each other. Person 0 sends to person 1, and person 1 sends to person 0. Total: 2 requests.

Example 2 — Multiple Ages

$ Input: ages = [16,17,18]

› Output: 2

💡 Note: Person aged 17 can send to 16 (17 > 0.5×17+7=15.5). Person aged 18 can send to 17 (18 > 0.5×18+7=16). Total: 2 requests.

Example 3 — No Valid Requests

$ Input: ages = [20,30,100,110,120]

› Output: 3

💡 Note: Only age 100 people can send requests among themselves. With 1 person of age 100, no requests are possible between different people.

Constraints

1 ≤ ages.length ≤ 2 × 10⁴
1 ≤ ages[i] ≤ 120

Visualization

Tap to expand

Understanding the Visualization

Input

Array of ages: [16, 17, 18]

Apply Rules

Check three conditions for each pair

Output

Count total valid friend requests: 2

Key Takeaway

🎯 Key Insight: Sort ages first, then use binary search to efficiently find valid age ranges for each person

Asked in

F Facebook 35 G Google 28 a Amazon 22

The key insight is that friend requests follow three age-based rules that can be optimized using sorting and binary search. The binary search approach sorts ages first, then for each person efficiently finds their valid age range using binary search. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Count	O(n log n)	O(n)	Sort ages first, then use frequency counting to optimize repeated comparisons
Binary Search Optimization	O(n log n)	O(1)	Sort ages and use binary search to find valid age ranges for each person
Brute Force	O(n²)	O(1)	Check every pair of people to see if a friend request should be sent

Sort and Count — Algorithm Steps

Sort the ages array
Count frequency of each unique age
For each unique age, find valid age range using the rules
Multiply valid targets by sender frequency
Sum all valid friend requests

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Group people by age and count occurrences

Check Age Pairs

For each unique age pair, apply friend request rules

Multiply by Count

Multiply valid connections by frequency counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct AgeCount {
    int age;
    int count;
};

int solution(int* ages, int n) {
    struct AgeCount ageCount[200];
    int uniqueAges = 0;
    
    // Count frequencies
    for (int i = 0; i < n; i++) {
        int found = 0;
        for (int j = 0; j < uniqueAges; j++) {
            if (ageCount[j].age == ages[i]) {
                ageCount[j].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            ageCount[uniqueAges].age = ages[i];
            ageCount[uniqueAges].count = 1;
            uniqueAges++;
        }
    }
    
    int requests = 0;
    
    for (int i = 0; i < uniqueAges; i++) {
        for (int j = 0; j < uniqueAges; j++) {
            int ageX = ageCount[i].age;
            int ageY = ageCount[j].age;
            int countX = ageCount[i].count;
            int countY = ageCount[j].count;
            
            if (ageX == ageY) {
                // Same age group: n*(n-1) pairs since can't send to self
                if (ageY > 0.5 * ageX + 7 && ageY <= ageX && !(ageY > 100 && ageX < 100)) {
                    requests += countX * (countY - 1);
                }
            } else {
                // Different age groups: check if ageX can send to ageY
                if (ageY > 0.5 * ageX + 7 && ageY <= ageX && !(ageY > 100 && ageX < 100)) {
                    requests += countX * countY;
                }
            }
        }
    }
    
    return requests;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int ages[200];
    int n = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            ages[n++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(ages, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then one pass through unique ages

⚡ Linearithmic

Space Complexity

O(n)

HashMap to store frequency counts of ages

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler