Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

ค้นหา N ตัวเลขที่แตกต่างกันซึ่งมีระดับบิตหรือเท่ากับ K ใน Python


สมมติว่าเรามีจำนวนเต็มสองจำนวน N และ K; เราต้องหาค่าที่ไม่ซ้ำ N ค่าซึ่งมี OR แบบ bit-wise เท่ากับ K หากไม่มีผลลัพธ์ดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น N =4 และ K =6 เอาต์พุตจะเป็น [6,0,1,2]

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

  • สูงสุด :=32

  • เข้าชมแล้ว :=รายการขนาด MAX และกรอกเป็นเท็จ

  • res :=รายการใหม่

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

  • จุด :=0

  • ค่า :=0

  • สำหรับผมอยู่ในช่วง 0 ถึง MAX ทำ

    • ถ้า visit[i] ไม่เป็นศูนย์ แล้ว

      • ไปทำซ้ำต่อไป

    • มิฉะนั้น

      • ถ้า num AND 1 ไม่ใช่ศูนย์ ดังนั้น

        • ค่า :=ค่า +(2^i)

      • num :=num/2 (ใช้เฉพาะส่วนจำนวนเต็ม)

  • ใส่ค่าที่ท้าย res

  • จากวิธีหลัก ให้ทำดังนี้ −

  • pow2 :=อาร์เรย์ของกำลัง 2 จาก 2^0 ถึง 2^31

  • ใส่ k ต่อท้าย res

  • cnt_k :=จำนวนบิตในหน่วย k

  • ถ้า pow2[cnt_k]

    • กลับ -1

  • นับ :=0

  • สำหรับฉันอยู่ในช่วง 0 ถึง pow2[cnt_k] - 1 ทำ

    • เพิ่ม(i)

    • นับ :=นับ + 1

    • ถ้านับเท่ากับ n แล้ว

      • ออกจากวง

  • ผลตอบแทน

ตัวอย่าง

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

MAX = 32
visited = [False for i in range(MAX)]
res = []
def set_bit_count(n):
   if (n == 0):
      return 0
   else:
      return (n & 1) + set_bit_count(n >> 1)
def add(num):
   point = 0
   value = 0
   for i in range(MAX):
      if (visited[i]):
         continue
      else:
         if (num & 1):
            value += (1 << i)
         num = num//2
   res.append(value)
def solve(n, k):
   pow2 = [2**i for i in range(MAX)]
   res.append(k)
   cnt_k = set_bit_count(k)
   if (pow2[cnt_k] < n):
      return -1
   count = 0
   for i in range(pow2[cnt_k] - 1):
      add(i)
      count += 1
      if (count == n):
         break
   return res

n = 4
k = 6
print(solve(n, k))

อินพุต

4, 6

ผลลัพธ์

[6, 0, 1, 2]