Đếm cặp Good Meals (tổng là lũy thừa của 2) Python

Mô tả bài toán

Cho mảng deliciousness, đếm số cặp (i, j) với i < j sao cho tổng deliciousness[i] + deliciousness[j] là lũy thừa của 2 (1, 2, 4, 8, 16, ...).

Ví dụ: [1, 3, 5, 7, 9] → 4 cặp: (1,3)=4, (1,7)=8, (3,5)=8, (7,9)=16.

Giải pháp tối ưu: Hash map + duyệt lũy thừa 2

Ý tưởng: Với mỗi phần tử x, tìm target = 2^k - x đã gặp trước đó.

from collections import defaultdict

def countPairs(deliciousness):
    MOD = 10**9 + 7
    count = defaultdict(int)
    ans = 0
    
    # Các lũy thừa 2 có thể (max sum = 2*max_val)
    max_val = max(deliciousness) if deliciousness else 0
    powers = []
    p = 1
    while p <= 2 * max_val:
        powers.append(p)
        p <<= 1  # nhân 2
    
    for d in deliciousness:
        for target_sum in powers:
            complement = target_sum - d
            ans = (ans + count[complement]) % MOD
        count[d] += 1
    
    return ans

# Test
print(countPairs([1, 3, 5, 7, 9]))       # 4
print(countPairs([1,1,1,3,3,3,7]))       # 15

Giải thích thuật toán

1. Duyệt từng phần tử d trong mảng.
2. Với mỗi lũy thừa 2 (1, 2, 4, 8...), tính complement = 2^k - d.
3. Nếu complement đã xuất hiện trước (trong count), cộng số lần xuất hiện vào kết quả.
4. Cập nhật count[d]++.

Độ phức tạp

• Time: O(n * log(max_val)) - n phần tử, log(max_val) lũy thừa 2.
• Space: O(n) - hash map lưu tần suất.

Code gốc có lỗi

Code mẫu trong đề bài có biến ans chưa khai báo, logic while sai. Code trên đã sửa hoàn chỉnh.