Friends Of Appropriate Ages: เพื่อนที่อายุเหมาะสมใน C++

ปัญหา

มีคนกลุ่มหนึ่งมีอายุใน ages[] คน A จะ ไม่ ส่ง Friend Request ให้ B (B ≠ A) ถ้า:

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

นอกจากนี้จะส่ง Request หาจำนวน Request ทั้งหมด

ตัวอย่าง: [16,17,18] → 2 Requests: 17→16, 18→17

แนวคิด: Bucket Count + Prefix Sum

เงื่อนไขที่ทำให้ A ส่ง Request ให้ B ได้

ตรงข้ามของข้อห้าม:

age[B] > 0.5 * age[A] + 7   AND
age[B] ≤ age[A]             AND
!(age[B] > 100 && age[A] < 100)

เงื่อนไขที่ 3: ถ้า A < 100 แล้ว B > 100 → ห้าม แต่ถ้า A ≥ 100 แล้ว B > 100 → ได้ (เพราะ age[B] ≤ age[A] บังคับอยู่แล้ว)

→ สรุป: age[B] ∈ (0.5*age[A]+7, age[A]]

Optimization: Frequency Array + Prefix Sum

อายุสูงสุด 120 (Constraints ทั่วไป) → ใช้ Array ขนาด 121

1. นับ Frequency: bucket[age]++
2. Prefix Sum: bucket[i] += bucket[i-1] → bucket[x] = จำนวนคนอายุ ≤ x
3. สำหรับแต่ละคนอายุ x:
   • y = x/2 + 7 (Lower bound)
   • ถ้า x > y: เพิ่ม bucket[x] - bucket[y]
   • ลบ 1 (ไม่ส่งให้ตัวเอง)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> bucket(121, 0);  // อายุ 0-120
        
        // Frequency
        for (int age : ages) bucket[age]++;
        
        // Prefix Sum
        for (int i = 1; i < 121; i++) {
            bucket[i] += bucket[i-1];
        }
        
        int ret = 0;
        for (int age : ages) {
            int y = age / 2 + 7;
            if (age > y) {
                ret += bucket[age] - bucket[y];
                ret--;  // ไม่ส่งให้ตัวเอง
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {16, 17, 18};
    cout << ob.numFriendRequests(v);  // 2
    return 0;
}

ความซับซ้อน

• Time: O(n + maxAge) = O(n)
• Space: O(maxAge) = O(1)

Input / Output

Input:  [16,17,18]
Output: 2