โปรแกรมหาผลรวมต่ำสุดโดยเปลี่ยนบิต 0 เป็น 1 จำนวน k ครั้งใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า k ต้องทำการดำเนินการ k ครั้ง: เลือกตัวเลขใดก็ได้ในลิสต์ เลือกบิตที่เป็น 0 ในการแทนค่าบाइनนารี แล้วเปลี่ยนเป็น 1 หาผลรวมต่ำสุดของทุกตัวเลขหลังทำ k ครั้ง ถ้าคำตอบสูงมาก ให้คืนค่า modulo 10^9+7

ตัวอย่าง

อินพุต: nums = [4, 7, 3], k = 2

เอาต์พุต: 17

4 = 100, 3 = 011, 7 = 111 ตั้งบิต 0 ของ 4 ให้เป็น 1 สองครั้ง (บิตที่ 1 และ 2) ได้ 111 = 7 ผลรวม = 7+7+3=17

ขั้นตอนการแก้ปัญหา

ใช้วิธี Greedy: ตั้งบิต 0 ที่มีน้ำหนักน้อยที่สุด (LSB) ก่อน:

1. ans = 0, i = 0
2. วนลูป while k > 0:
   • วนลูปผ่านทุก n ใน nums:
     • ถ้า (n >> i) & 1 == 0 (บิตที่ i เป็น 0):
       • ans += 1 << i
       • k -= 1
       • ถ้า k == 0 break
   • i += 1
3. คืนค่า (ans + sum(nums)) % (10**9+7)

การนำไปใช้ใน Python

class Solution:
    def solve(self, nums, k):
        m = (10 ** 9 + 7)
        ans = 0
        i = 0
        while k:
            for n in nums:
                if (n >> i) & 1 == 0:
                    ans += 1 << i
                    k -= 1
                    if k == 0:
                        break
            i += 1
        return (ans + sum(nums)) % m

ob = Solution()
nums = [4, 7, 3]
k = 2
print(ob.solve(nums, k))

อินพุต

[4, 7, 3], 2

เอาต์พุต

17