【ITニュース解説】🎿“Minimum Operations to Make the Integer Zero” LeetCode: 2749 [C++, JavaScript, Python]

LeetCodeの問題2749「Minimum Operations to Make the Integer Zero」は、与えられた2つの整数num1とnum2を用いて、num1を0にするために必要な最小操作回数を求める問題だ。操作は、num1から(2^i + num2)を引くというもので、iは0から60までの任意の整数を選べる。num1を0にできない場合は-1を返す。

この問題を解くための核心は、操作を繰り返した結果を理解することにある。k回の操作を行った後、num1から引かれる値は、(2^i1 + num2) + (2^i2 + num2) + ... + (2^ik + num2)となる。これを整理すると、(k個の2のべき乗の和) + (k * num2)となる。つまり、k回の操作後、num1 - (k個の2のべき乗の和) - (k * num2) = 0となることを目指す。

この式を変形すると、num1 - k * num2 = (k個の2のべき乗の和)となる。ここで、T = num1 - k * num2と定義すると、問題は「Tをちょうどk個の2のべき乗の和で表現できるか？」という問いに置き換えられる。

この問いに対する答えを見つけるために、以下の3つのルールが重要になる。

1. Tは正の数でなければならない。なぜなら、正の2のべき乗の和は0以下にはならないからだ。
2. 項の数が重要である。ある数を表現するために必要な最小の2のべき乗の数は、その数の二進数表現における1の数（popcount）に等しい。したがって、popcount(T) <= kでなければならない。
3. k個の2のべき乗の最小の和はk (1 + 1 + ...のようにすべて1を使う) である。したがって、k <= Tでなければならない。

これらのルールに基づき、解決策は以下のようになる。

1. kを1から60までループする。なぜ60までかというと、iは最大60までしか許容されず、2^60はnum1の制限よりもはるかに大きくなるからだ。
2. 各kについて、T = num1 - k * num2を計算する。
3. Tが正の数でなければ、スキップする。
4. popcount(T) <= k <= Tならば、kは有効な操作回数であり、kを返す。

ループが完了しても有効なkが見つからない場合は、-1を返す。

例として、num1 = 3, num2 = -2の場合を考える。

• k = 1の場合: T = 3 - (1 * -2) = 5。popcount(5) = 2。しかし、2 > 1なので無効。
• k = 2の場合: T = 3 - (2 * -2) = 7。popcount(7) = 3。しかし、3 > 2なので無効。
• k = 3の場合: T = 3 - (3 * -2) = 9。popcount(9) = 2。2 <= 3 <= 9なので有効！

したがって、答えは3となる。

num1 = 5, num2 = 7の場合を考える。

• k = 1の場合: T = 5 - 7 = -2。無効。
• k = 2の場合: T = 5 - 14 = -9。無効。

kが大きくなるにつれて、Tはより小さくなる（より負になる）。したがって、解は存在しないため、答えは-1となる。

この解法が有効な理由は、二進数の性質に基づいているからだ。すべての正の整数は一意の二進数形式を持ち、その形式における1の数は、必要な最小の2のべき乗の数を示す。より多くの項が必要な場合は、大きなべき乗を小さなべき乗に分割できる。しかし、popcountよりも少ない項が必要な場合は、不可能となる。

この問題は、二進数の数学と注意深い推論が見事に組み合わさっている。最初は、操作(2^i + num2)が奇妙に感じられるが、分解してみると、主なタスクは、ある数を正確にk個の2のべき乗の和として表現できるかどうかを判断することであることが明確になる。重要なポイントは、Tの正の数であるかどうかの確認、popcountを下限として使用、T自体を上限として使用、そして60回までの操作のみを確認することである。