โปรแกรมนับคู่ดัชนีที่องค์ประกอบรวมเป็นกำลัง 2 ใน Python

สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums เราต้องหาจำนวนคู่ดัชนี i, j โดยที่ i =k.

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1, 2, 6, 3, 5] ผลลัพธ์จะเป็น 3 เนื่องจากมีสามคู่ผลรวมเช่น (6, 2):ผลรวมคือ 8, (5, 3) :ผลรวมคือ 8 และ (1, 3) ผลรวมคือ 4

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

• res :=0

• c :=แผนที่ที่มีความถี่ของแต่ละองค์ประกอบที่มีอยู่ใน

• สำหรับแต่ละ x เป็นตัวเลข ทำ

  • สำหรับ j ในช่วง 0 ถึง 31 ทำ

    • 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]

ผลลัพธ์

3