【ITニュース解説】C# LeetCode 268: Missing Number - (Easy)

プログラミング学習では、様々な問題解決のテクニックを身につけることが重要だ。今回は、与えられた数字の集まりの中から、一つだけ足りない数字を見つけ出すという問題を例に、プログラミング的な思考と数学的なアプローチの組み合わせを学ぶ。

まず、この問題がどのような状況を想定しているのかを詳しく見ていこう。君に与えられるのは「配列」と呼ばれる、いくつかの数字が順番に並んだデータ構造だ。この配列には、ある特定のルールに基づいて数字が格納されている。そのルールとは、「0からnまでの異なる数字が全て含まれているはずなのに、なぜか一つだけ数字が欠けている」というものだ。例えば、nが3だとすると、本来は0, 1, 2, 3という4つの数字が配列に含まれているはずだ。しかし、この問題ではそのうちのどれか一つ、例えば2が欠けていて、配列には[0, 3, 1]のように3つの数字だけが入っている状態を考える。ここで非常に重要なのは、「n」という値が、単に配列の長さ（要素の数）であると同時に、「期待される数字の範囲の最大値」でもあるという点だ。つまり、もし配列の長さが3であれば、それは0から3までの数字（0, 1, 2, 3）が対象となっている、という意味になる。この「n」の二重の意味を正しく理解することが、この問題を解く上で非常に大切なポイントとなる。

さて、どうすればこの欠けている数字を効率的に見つけられるだろうか。手当たり次第に数字をチェックしていく方法も考えられるが、もっとスマートな方法を検討したい。ここで注目するのは、「本来あるべき数字の集まり」と「実際に与えられた数字の集まり」の間に生じる「差」だ。もし、本来あるべき全ての数字がわかっていれば、その合計を計算できる。そして、実際に与えられた配列に含まれる数字の合計も計算できる。この二つの合計を比較すれば、その差がちょうど欠けている数字になるはずだ、という直感的なアイデアが浮かぶ。

このアイデアを実現するために、私たちは数学の有名な公式を使う。それは「ガウスの公式」として知られるもので、1からある数nまでの全ての自然数を足し合わせた合計を簡単に求めることができる公式だ。その公式は「Sum = n * (n + 1) / 2」と表される。この公式は非常に強力で、例えば1から100までの数字の合計を計算したい場合、1+2+...+100と一つずつ足していく代わりに、100 * (100 + 1) / 2 = 5050と一瞬で答えを導き出せる。なぜこの公式が成り立つのか、簡単に見てみよう。例えば1から100までの数字を足すことを考えると、1と100を足すと101、2と99を足すと101、3と98を足すと101、というように、両端から数字をペアにして足していくと、全てのペアが同じ合計値（この場合は101）になることに気づく。このようなペアは全部でいくつあるだろうか。100個の数字がある場合、ペアは50組（100 / 2）できる。つまり、101が50回繰り返されるので、101 * 50 = 5050となる。この考え方を一般化したものがガウスの公式なのだ。n * (n + 1) の部分で、ペアの合計値である (n + 1) と、もしペアの数が n 個だったらという仮定での積を求める。しかし実際にはペアは n/2 個しかないので、最後に2で割ることで正しい合計値が得られる。この問題では0からnまでの数字を扱うが、0を足しても合計は変わらないため、実質的には1からnまでの合計を計算するガウスの公式がそのまま適用できる。

ガウスの公式を使って「本来あるべき数字の合計（期待される合計）」を計算できるようになった。次に、実際に与えられた配列に含まれる数字の合計（実際の合計）を計算する。この二つの合計値が手に入れば、あとは非常に簡単だ。期待される合計から実際の合計を引けば、それがそのまま欠けている数字となる。 欠けている数字 = 期待される合計 - 実際の合計

この考え方を実際のプログラミングコード、ここではC#という言語でどのように表現するかを見ていこう。

Copy
1public int MissingNumber(int[] nums)
2{
3    int n = nums.Length;
4    int expectedSum = n * (n + 1) / 2;
5    int actualSum = 0;
6
7    foreach (int num in nums)
8    {
9        actualSum += num;
10    }
11
12    return expectedSum - actualSum;
13}

このコードは、「MissingNumber」という名前の機能（メソッドと呼ぶ）を定義している。この機能は、numsという名前の配列（整数型）を受け取り、欠けている数字を整数型で返す。 まず、int n = nums.Length;の行で、配列numsの長さ（要素の数）をnという変数に格納する。これが、ガウスの公式で使う「n」の値であり、同時に「0からnまでの数字が期待される」という範囲の最大値にもなる。 次に、int expectedSum = n * (n + 1) / 2;の行で、ガウスの公式を使って、本来0からnまでの数字が全て揃っていた場合の合計値を計算し、expectedSumという変数に格納する。 その後、int actualSum = 0;の行で、実際の配列の合計を計算するための変数actualSumを0で初期化する。 foreach (int num in nums)という部分は「ループ」と呼ばれる処理だ。配列numsの中にある数字を一つずつ取り出し、その数字をnumという変数に代入しながら、波括弧{}の中の処理を繰り返す。ループの中で行われるactualSum += num;という処理は、取り出した数字numをactualSumに足し合わせることを意味する。これにより、配列numsに含まれる全ての数字の合計がactualSumに累積されていく。 最後に、return expectedSum - actualSum;の行で、計算されたexpectedSumからactualSumを引いた結果を、この機能の答えとして返す。これが、まさに欠けている数字となる。

具体的な例で、このコードがどのように動作するかを確認しよう。例えば、numbers = [0, 3, 1]という配列が与えられたとする。 まず、nums.Lengthによって配列の長さが計算される。[0, 3, 1]の要素は3つなので、nは3となる。これは「0から3までの数字（0, 1, 2, 3）が対象である」ことを意味する。 次に、expectedSumを計算する。ガウスの公式 n * (n + 1) / 2 を使うので、3 * (3 + 1) / 2 となる。計算すると 3 * 4 / 2 = 12 / 2 = 6 となる。つまり、0, 1, 2, 3が全て揃っていれば合計は6になるはず、ということだ。 次に、actualSumを計算する。foreachループを使って、配列[0, 3, 1]の中の数字を一つずつ足し合わせる。0 + 3 + 1 = 4となる。 最後に、expectedSumからactualSumを引く。6 - 4 = 2。 したがって、欠けている数字は2であると導き出される。実際に[0, 3, 1]を見てみると、0, 1, 3はあるが2がないので、この結果は正しいことがわかる。

この問題は、一見すると複雑そうに見えるかもしれないが、数学の知識とプログラミングの基本的な考え方を組み合わせることで、非常に簡潔かつ効率的に解決できることがわかる。ここで学んだ「問題の条件を正しく理解すること（特にnの意味）」「数学的な公式をプログラミングに応用すること」「配列の要素を一つずつ処理するループの活用」といったスキルは、システムエンジニアとして様々な問題に取り組む上で非常に基礎的かつ重要なものとなるだろう。これらの考え方を身につけることは、より複雑な問題に挑戦していくための第一歩となる。