【Python】リスト内の数値の0ビットをk回1に変更して最小の合計を求める方法

数値のリスト nums と整数 k が与えられたとします。私たちが行うのは、次の操作をちょうど k 回繰り返すことです。リストから任意の数値を1つ選び、その数値の2進表現の中で「0」になっているビットを1つ選んで「1」に変更します。すべての操作を終えた後の全要素の合計として考えられる最小値を返してください。答えが非常に大きくなる場合は、10^9+7 で割った余りを結果として返します。

例として、nums = [4, 7, 3]、k = 2 の場合を見てみましょう。各数値の2進表現は、4 が 100、3 が 011、7 が 111 です。2つのビットを「1」に設定する必要がありますが、合計の増加を最小限に抑えるには、できるだけ小さい桁（下位ビット）の0から順に埋めるのが最適です。ここでは 4 の下位2桁を立てて 111（つまり 7）にすればよく、このとき合計は 7 + 7 + 3 = 17 となり、これが最小値になります。

解法のアプローチ

この問題は貪欲法で解くことができます。i 桁目のビットを 0 から 1 に変更すると、その数値はちょうど 2^i だけ増えるため、増加分を最小にするには小さい桁から順に「0」のビットを埋めていくのが最適だからです。具体的な手順は以下のとおりです。

• ans := 0、i := 0 と初期化します。

• k が 0 でない間、次の処理を繰り返します。

• リスト内の各要素 n について、(n / 2^i) が偶数（つまり i 桁目のビットが 0）であれば、ans に 2^i を加算し、k を 1 減らします。

• k が 0 になった時点で、内側のループを抜けます。

• i を 1 増やして、次の桁へ処理を進めます。

最後に、ans に元のリストの全要素の合計を加え、m = 10^9+7 で割った余りを返します。実装上のポイントは、桁位置 i を while ループの末尾で必ずインクリメントすることです。そうしないと同じ桁を何度も調べてしまい、無限ループに陥ります。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

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

出力が 17 になる理由は、4 の下位2桁（1の位と2の位）の0を立てて 4 → 7 と変換でき、合計が 7 + 7 + 3 = 17 となるためです。

計算量

各桁ごとにリスト全体を走査するため、時間計算量は O(k × N)（N はリストの長さ）程度、追加で必要な空間計算量は O(1) です。