Chương trình đếm các cặp với XOR trong một phạm vi bằng Python

Giả sử chúng ta có một dãy nums và có hai giá trị l và r, chúng ta phải tìm số cặp đẹp. Ở đây một cặp đẹp là một cặp (i, j) trong đó 0 <=i

Vì vậy, nếu đầu vào là nums =[4,1,7,2] l =2 r =6, thì đầu ra sẽ là 6 vì các cặp đẹp là (1,0):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.

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

• Xác định một bài kiểm tra hàm (). Điều này sẽ mất nums, x

• count:=một bản đồ chứa tần số của các phần tử tính bằng nums

• res:=0

• trong khi x là khác 0, thực hiện

  • nếu x là số lẻ thì

    • res:=res + tổng tất cả các phần tử của (count [a] * count [(x - 1) XOR a) cho tất cả a được đếm

  • count:=bản đồ với khóa a / 2 và giá trị (count [a] + count [a XOR 1] cho tất cả a được đếm

  • x =thương số của x / 2

• trả về thương số của res / 2

• Từ kiểm tra trả về phương thức chính (nums, r + 1) - kiểm tra (nums, l)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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

Đầu vào

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

Đầu ra

6