Friends Of Appropriate Ages

medium array counting two-pointers

Problem

Person x sends a request to person y (x != y) unless y.age <= 0.5*x.age + 7, y.age > x.age, or y.age > 100 and x.age < 100. Count the total number of friend requests.

Inputages = [16,17,18]

Output2

17 -> 16 and 18 -> 17 are the only valid requests.

input

def numFriendRequests(ages):
    count = [0] * 121
    for a in ages: count[a] += 1
    res = 0
    for a in range(1, 121):
        for b in range(1, 121):
            if b <= 0.5 * a + 7: continue
            if b > a: continue
            if b > 100 and a < 100: continue
            res += count[a] * count[b]
            if a == b: res -= count[a]
    return res

function numFriendRequests(ages) {
  const count = new Array(121).fill(0);
  for (const a of ages) count[a]++;
  let res = 0;
  for (let a = 1; a <= 120; a++) {
    for (let b = 1; b <= 120; b++) {
      if (b <= 0.5 * a + 7) continue;
      if (b > a) continue;
      if (b > 100 && a < 100) continue;
      res += count[a] * count[b];
      if (a === b) res -= count[a];
    }
  }
  return res;
}

class Solution {
  public int numFriendRequests(int[] ages) {
    int[] count = new int[121];
    for (int a : ages) count[a]++;
    int res = 0;
    for (int a = 1; a <= 120; a++) {
      for (int b = 1; b <= 120; b++) {
        if (b <= 0.5 * a + 7) continue;
        if (b > a) continue;
        if (b > 100 && a < 100) continue;
        res += count[a] * count[b];
        if (a == b) res -= count[a];
      }
    }
    return res;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> count(121, 0);
        for (int a : ages) count[a]++;
        int res = 0;
        for (int a = 1; a <= 120; a++) {
            for (int b = 1; b <= 120; b++) {
                if (b <= 0.5 * a + 7) continue;
                if (b > a) continue;
                if (b > 100 && a < 100) continue;
                res += count[a] * count[b];
                if (a == b) res -= count[a];
            }
        }
        return res;
    }
};

Explanation

Comparing every person with every other person would be slow when there are many people. The key observation is that only the age matters, not who the person is — two 17-year-olds behave identically. So instead of looping over people, we loop over ages.

First we build a count array: count[a] is how many people are age a. Ages only go up to 120, so this is a small fixed-size bucket list regardless of how many people there are.

Then we try every pair of ages (a, b) where a is the sender and b is the receiver. A request is valid unless one of the three rules blocks it: b <= 0.5*a + 7, b > a, or b > 100 and a < 100. If the pair is allowed, every person of age a sends to every person of age b, so we add count[a] * count[b].

One subtlety: when a == b a person cannot friend themselves, so we subtract count[a] to remove those self-requests.

Example: ages = [16, 17, 18]. The only allowed pairs turn out to be 17 sending to 16 and 18 sending to 17, giving a total of 2 requests. Because the outer loops run only over the 120 possible ages, the work no longer grows with the crowd size beyond the initial counting pass.

Time: O(n + A^2) Space: O(A)