Python의 범위에서 XOR로 쌍을 계산하는 프로그램

<시간/>

배열 nums가 있고 두 개의 값 l과 r이 있다고 가정하면 nice 쌍의 수를 찾아야 합니다. 여기서 좋은 쌍은 쌍(i, j)입니다. 여기서 0 <=i

따라서 입력이 nums =[4,1,7,2] l =2 r =6과 같으면 좋은 쌍이 (1,0)이므로 출력은 6이 됩니다. 1 XOR 4 =5, (1 ,2):1 XOR 7 =6, (1,3):1 XOR 2 =3, (0,3):4 XOR 2 =6, (0,2):4 XOR 7 =3,(2,3 ):7 XOR 2 =5.

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

test() 함수를 정의합니다. 숫자 x
가 필요합니다.
count :=요소의 빈도를 숫자로 포함하는 맵
해상도 :=0
x가 0이 아닌 동안 수행
- x가 홀수이면
  - res :=res + 모든 in count에 대한 (count[a] * count[(x - 1) XOR a) 모든 요소의 합계
- count :=키 a/2 및 값이 있는 맵(count[a] + count[a XOR 1] 모든 a에 대한 카운트
- x =x/2의 몫
res / 2의 몫을 반환
기본 메서드에서 test(nums, r + 1) - test(nums, l)
를 반환합니다.

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다.

from collections import Counter
def solve(nums, l, r):
   def test(nums, x):
      count = Counter(nums)
      res = 0
      while x:
         if x & 1:
            res += sum(count[a] * count[(x - 1) ^ a] for a in count)
         count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
         x >>= 1
      return res // 2

   return test(nums, r + 1) - test(nums, l)

nums = [4,1,7,2]
l = 2
r = 6
print(solve(nums, l, r))

입력

[4,1,7,2], 2, 6