โปรแกรมนับคู่ดัชนีที่ผลรวมเป็นกำลังของ 2 ใน Python

การนับคู่ดัชนี (i, j) ที่ผลรวมเป็น 2^k

กำหนดให้ i < j หาจำนวนคู่ที่ nums[i] + nums[j] = 2^k สำหรับ k >= 0

อัลกอริทึม

1. ใช้ Counter นับความถี่ของตัวเลขที่ผ่านมาแล้ว
2. วนลูปแต่ละตัวเลข x ใน nums
3. สำหรับ k = 0 ถึง 31 (ครอบคลุมช่วง int 32-bit) ตรวจสอบว่า (2^k - x) เคยเจอมาก่อนหรือไม่
4. เพิ่มจำนวนคู่ที่พบ
5. อัปเดตความถี่ของ x

ตัวอย่างโค้ด

from collections import Counter

def solve(nums):
    res, c = 0, Counter()
    for x in nums:
        for j in range(32):
            res += c[(1 << j) - x]
        c[x] += 1
    return res

nums = [1, 2, 6, 3, 5]
print(solve(nums))

ผลลัพธ์

3

คำอธิบายคู่ที่พบ

• (6, 2) → 8 = 2^3
• (5, 3) → 8 = 2^3
• (1, 3) → 4 = 2^2

ความซับซ้อน

Time: O(n * 32) ≈ O(n), Space: O(n)