Chương trình đếm các cặp chỉ số mà tổng 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ố được gọi là nums. Chúng ta phải tìm số cặp chỉ mục i, j, trong đó i =k.

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):sum 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 tôi sẽ làm theo các bước sau -

• res:=0

• c:=một bản đồ chứa tần số của từng phần tử có trong

• đối với mỗi x trong số, thực hiện

  • đối với j trong phạm vi từ 0 đến 31, thực hiện

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

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

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để 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