โปรแกรมนับคู่กับ XOR ในช่วงใน Python

สมมติว่าเรามีจำนวนอาร์เรย์และมีค่าสองค่า l และ r เราต้องหาจำนวนคู่ที่ดี นี่เป็นคู่ที่ดีคือคู่ (i, j) โดยที่ 0 <=i

ดังนั้น หากอินพุตเท่ากับ nums =[4,1,7,2] l =2 r =6 ผลลัพธ์จะเป็น 6 เพราะคู่ที่ดีคือ (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.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน test() นี่จะใช้เวลา num, x

• count :=แผนที่ที่มีความถี่ขององค์ประกอบเป็น nums

• res :=0

• ในขณะที่ x ไม่ใช่ศูนย์ให้ทำ

  • ถ้า x เป็นเลขคี่

    • res :=res + ผลรวมขององค์ประกอบทั้งหมดของ (count[a] * count[(x - 1) XOR a) สำหรับ a ทั้งหมดในการนับ

  • count :=map พร้อมคีย์ a/2 และค่า (count[a] + count[a XOR 1] สำหรับทุก a in count

  • x =ผลหารของ x/2

• ผลตอบแทนของ res / 2

• จากวิธีหลัก return 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

ผลลัพธ์

6