파이썬에서 요소 합이 2의 거듭제곱인 인덱스 쌍을 계산하는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정합니다. 인덱스 쌍 i, j의 수를 찾아야 합니다. 여기서 i =k에 대해 2^k와 같도록 합니다.

따라서 입력이 nums =[1, 2, 6, 3, 5]와 같으면 출력은 3이 됩니다. (6, 2)와 같은 세 쌍의 합이 있기 때문입니다. 합은 8, (5, 3) :합은 8이고 (1, 3) 합은 4입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

해상도 :=0
c :=
에 있는 각 요소의 빈도를 포함하는 맵
숫자의 각 x에 대해 수행
- 범위 0에서 31까지의 j에 대해 수행
  - res :=res + c[(2^j) - x]
- c[x] :=c[x] + 1
반환 해상도

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

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

입력

[1, 2, 6, 3, 5]