โปรแกรมค้นหาค่า XOR ขององค์ประกอบเฉพาะจากรายการที่สร้างใน Python

สมมติว่าเราได้รับรายการที่มีตัวเลขธรรมชาติ ตอนนี้จากรายการนั้น เราลบตัวเลขทั้งหมดที่มีเลข 1 สองตัวติดต่อกันในการแทนค่าไบนารี และสร้างรายการอื่นที่เรียกว่า Z ตอนนี้เราได้รับ 'input_list' อีกรายการหนึ่งที่มีค่าจำนวนเต็มบางค่า เราต้องหาค่า XOR ขององค์ประกอบที่ระบุจาก Z ซึ่งมีการระบุดัชนีใน input_list

ดังนั้น หากอินพุตเป็นเหมือน input_list =[3, 4, 5] ผลลัพธ์จะเป็น 9

ในดัชนี 3, 4 และ 5 ของ Z; ค่าคือ 4, 5 และ 8 ดังนั้น 4 XOR 5 XOR 8 =9

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

• กำหนดฟังก์ชัน zeck_num() นี่จะใช้เวลา k, f_list
  • res :=0
  • สำหรับ i ในช่วง (ขนาดของ f_list -1) ถึง -1, ลดลง 1, ทำ
    • ถ้า k>=f_list[i] แล้ว
      • res :=res + 2^i
      • k :=k - f_list[i]
  • ผลตอบแทน
• MOD :=10^9 + 7
• max_val :=10^18
• f_list :=รายการใหม่ที่มีค่า 1 และ 2
• ในขณะที่องค์ประกอบสุดท้ายของ f_list <=max_val ทำ
  • แทรกองค์ประกอบสุดท้ายของ f_list + องค์ประกอบสุดท้ายที่สองของ f_list ที่ส่วนท้ายของ f_list
• res :=0
• สำหรับแต่ละดัชนีใน input_list ให้ทำ
  • res :=res XOR zeck_num(index, f_list)
• รีเทิร์น res mod MOD

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def zeck_num(k, f_list):
   res = 0
   for i in range(len(f_list)-1,-1,-1):
      if k >= f_list[i]:
         res += 2**i
         k -= f_list[i]
   return res

def solve(input_list):
   MOD = 10**9+7
   max_val = 10**18
   f_list = [1,2]
   while f_list[-1] <= max_val:
      f_list.append(f_list[-1] + f_list[-2])
   res = 0
   for index in input_list:
      res ^= zeck_num(index, f_list)
   return res % MOD

print(solve([3, 4, 5]))

อินพุต

[3, 4, 5]

ผลลัพธ์

9