Python程式：透過k次將0改為1來找到數字列表的最小可能和？

假設我們有一個名為nums的數字列表和另一個值k。我們需要執行以下操作k次：選擇列表中的任何數字。在該數字的二進位制表示中，選擇一個為0的位並將其設為1。最後，我們需要返回執行k次操作後所有數字的最小可能和。如果答案過大，則返回結果模10^9+7。

因此，如果輸入類似於nums = [4, 7, 3] k = 2，則輸出將為17，因為4的二進位制表示為100，3為011，7為111。由於我們需要設定2位，我們可以設定4的位使其變為111（7）。然後總和為7 + 7 + 3 = 17。

為了解決這個問題，我們將遵循以下步驟

ans := 0, i := 0
當k非零時，執行
- 對於nums中的每個n，執行
  - 如果(n / 2^i)為偶數，則
    - ans := ans + 2^i
    - k := k - 1
    - 如果k等於0，則
      - 退出迴圈
- i := i + 1
返回 (ans + nums所有元素的和) mod m

讓我們看看下面的實現來更好地理解

示例

線上演示

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

輸出

Arnab Chakraborty

更新於：2020年11月10日

85 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習