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

输出

17

更新于：2020年11月10日

85 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告