Chương trình tìm tổng nhỏ nhất sau khi đổi bit 0 thành 1 k lần trong Python

Cho danh sách số nums và số k. Thực hiện k lần: chọn một số, chọn một bit 0 trong biểu diễn nhị phân của nó, đổi thành 1. Tìm tổng nhỏ nhất có thể sau k phép toán. Kết quả modulo 10⁹+7.

Ví dụ

nums = [4, 7, 3], k = 2

Nhị phân: 4=100, 7=111, 3=011

Đổi 2 bit 0 thấp nhất của 4 (bit 0 và bit 1) → 4 thành 111 (7). Tổng = 7+7+3 = 17.

Thuật toán (Greedy bit thấp nhất)

1. Duyệt bit từ thấp (i=0) đến cao.
2. Với mỗi bit i, duyệt tất cả số n trong nums:
   • Nếu bit i của n là 0: đổi thành 1 (cộng 2ⁱ vào kết quả), k--.
   • Nếu k == 0: dừng.
3. Kết quả = (sum(nums) + added) % MOD.

Chiến lược tham lam bit thấp nhất cho tổng tăng thêm nhỏ nhất.

Triển khai Python

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

# Test
ob = Solution()
print(ob.solve([4, 7, 3], 2))  # Output: 17

Độ phức tạp

• Thời gian: O(k + n × log(max_num)) - thực tế rất nhanh vì k thường nhỏ.
• Không gian: O(1).