Skip to content

825. Friends Of Appropriate Ages 👎

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int numFriendRequests(vector<int>& ages) {
    int ans = 0;
    unordered_map<int, int> count;

    for (const int age : ages)
      ++count[age];

    for (const auto& [ageA, countA] : count)
      for (const auto& [ageB, countB] : count)
        if (request(ageA, ageB))
          if (ageA == ageB)
            ans += countA * (countB - 1);
          else
            ans += countA * countB;

    return ans;
  }

 private:
  bool request(int ageA, int ageB) {
    return !(ageB <= 0.5 * ageA + 7 || ageB > ageA || ageB > 100 && ageA < 100);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int numFriendRequests(int[] ages) {
    int ans = 0;
    int[] count = new int[121];

    for (final int age : ages)
      ++count[age];

    for (int ageA = 1; ageA <= 120; ++ageA)
      for (int ageB = 1; ageB <= 120; ++ageB) {
        final int countA = count[ageA];
        final int countB = count[ageB];
        if (countA > 0 && countB > 0 && request(ageA, ageB))
          if (ageA == ageB)
            ans += countA * (countB - 1);
          else
            ans += countA * countB;
      }

    return ans;
  }

  private boolean request(int ageA, int ageB) {
    return !(ageB <= 0.5 * ageA + 7 || ageB > ageA || ageB > 100 && ageA < 100);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def numFriendRequests(self, ages: List[int]) -> int:
    ans = 0
    count = [0] * 121

    for age in ages:
      count[age] += 1

    for i in range(15, 121):
      ans += count[i] * (count[i] - 1)

    for i in range(15, 121):
      for j in range(i // 2 + 8, i):
        ans += count[i] * count[j]

    return ans