Chương trình đếm cặp chỉ số mà tổng các phần tử là lũy thừa của 2 trong Python

Giả sử chúng ta có một danh sách các số gọi là nums. Chúng ta phải tìm số cặp chỉ số i, j, với i < j sao cho nums[i] + nums[j] bằng 2^k với k >= 0.

Vì vậy, nếu đầu vào là nums = [1, 2, 6, 3, 5], thì đầu ra sẽ là 3, vì có ba cặp tổng như (6, 2): tổng là 8, (5, 3): tổng là 8 và (1, 3) tổng là 4.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

• res := 0

• c := một map chứa tần suất của mỗi phần tử hiện có trong nums

• với mỗi x trong nums, thực hiện

  • với j trong khoảng 0 đến 31, thực hiện

    • res := res + c[(2^j) - x]

  • c[x] := c[x] + 1

• trả về res

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

[1, 2, 6, 3, 5]

Đầu ra

3