algoadvance

Leetcode 825. Friends Of Appropriate Ages

Problem Statement

  1. Friends Of Appropriate Ages

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the i-th person.

Rules for making friends are that age A will not friend request age B if any of the following is true:

  1. age[B] <= 0.5 * age[A] + 7
  2. age[B] > age[A]
  3. age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Given the list of ages, return the total number of friend requests made.

Example 1:

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Note:

Clarifying Questions

  1. Should we consider only one direction of friendship (A -> B) or both directions (A -> B and B -> A)?
    • From the examples, it seems we consider each direction separately, thus each valid pair is counted once per valid direction.
  2. Do ages include all values between 1 and 120 inclusively?
    • Yes, ages[i] where 1 <= ages[i] <= 120.

Strategy

  1. Count Occurrences of Each Age: Use a frequency array to count occurrences of each age between 1 and 120.
  2. Traverse Pairs of Ages: Traverse each pair of ages (ageA, ageB) using two nested loops. Use the criteria given to check if one can send a friend request to the other.
  3. Count Valid Friend Requests: If ageA can send a friend request to ageB and vise-versa, count the total valid friend requests considering the frequency of each age.

Code

Here is the C++ implementation of the described strategy:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int freq[121] = {0}; // Array to store frequency of ages from 1 to 120

        // Count the frequency of each age
        for (int age : ages) {
            freq[age]++;
        }

        int totalRequests = 0;

        // Check all pairs of possible ages
        for (int ageA = 1; ageA <= 120; ageA++) {
            for (int ageB = 1; ageB <= 120; ageB++) {
                if (freq[ageA] > 0 && freq[ageB] > 0) {  // if there are people of ageA and ageB
                    if (ageB <= 0.5 * ageA + 7 || ageB > ageA || (ageB > 100 && ageA < 100)) {
                        continue; // B cannot receive a friend request from A
                    }
                    if (ageA == ageB) {
                        totalRequests += freq[ageA] * (freq[ageB] - 1); // A cannot friend request itself
                    } else {
                        totalRequests += freq[ageA] * freq[ageB];
                    }
                }
            }
        }

        return totalRequests;
    }
};

Time Complexity

  1. Time Complexity:
    • Counting frequency takes (O(n)), where (n) is the number of ages in the input.
    • Checking all pairs of ages in the nested loops takes (O(120^2) \approx O(1)) since 120 is a constant limit.
    • Thus, the overall time complexity is (O(n)), which is efficient given the problem constraints.
  2. Space Complexity:
    • We use an additional array of fixed size (121), so the space complexity is (O(1)).

This solution efficiently counts the valid friend requests according to the given rules.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI