We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Friends Of Appropriate Ages

Number: 852

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

There are n persons on a social media website. Given an integer array ages where ages[i] is the age of the iᵗʰ person, person x will send a friend request to person y (with x ≠ y) if the following conditions are all met:

  • age[y] > 0.5 * age[x] + 7
  • age[y] ≤ age[x]
  • It is not the case that age[y] > 100 and age[x] < 100. Return the total number of friend requests made.

Key Insights

  • The friend request condition can be simplified to checking that age[y] > 0.5 * age[x] + 7 and age[y] ≤ age[x].
  • Given that ages are within the range [1, 120], a frequency array of fixed size (e.g., 121 elements) can be used.
  • Instead of comparing every pair, count the frequency of each age and then iterate over possible age pairs to compute the valid friend requests.
  • If both persons have the same age, subtract self-requests since a person cannot send a friend request to themselves.

Space and Time Complexity

Time Complexity: O(120^2) ≈ O(1) when using the frequency approach due to the constant bounded range of ages. Space Complexity: O(1) since we use a fixed size array (size 121) for counting frequencies.

Solution

The solution involves first counting the number of individuals for each age. For each possible age a and for every age b from 15 to a (since ages below 15 will not satisfy the condition for most a’s), if b is greater than 0.5 * a + 7, then all individuals of age a can potentially send friend requests to all individuals of age b. If a and b are the same, we subtract self-requests by using count[a] * (count[a] - 1); otherwise, we add count[a] * count[b].

Code Solutions

# Python solution using a frequency array and nested loops

def numFriendRequests(ages):
    # Frequency array for ages 1 to 120
    count = [0] * 121
    for age in ages:
        count[age] += 1
    
    total_requests = 0
    # Iterate over possible sender age 'a' starting from 15
    for a in range(15, 121):
        if count[a] == 0:
            continue
        # Iterate over possible receiver age 'b'
        for b in range(15, a+1):  # Ensure b <= a
            if count[b] == 0:
                continue
            # Check valid request condition
            if b <= 0.5 * a + 7:
                continue
            # If both ages are the same, subtract self friend requests
            if a == b:
                total_requests += count[a] * (count[a] - 1)
            else:
                total_requests += count[a] * count[b]
    return total_requests

# Example usage:
print(numFriendRequests([16, 16]))  # Expected output: 2
← Back to All Questions