N回の操作後に配列に残る「1」の個数を数えるアルゴリズム【C言語】

問題概要

サイズNの整数型配列が与えられ、初期状態ではすべての要素が0です。ここで、合計N回の操作を行った後、配列内に「1」がいくつ残っているかを求めるのが課題です。各操作には次のようなルールが定められています。

• 1回目の操作：位置1, 2, 3, 4, … の要素を反転する
• 2回目の操作：位置2, 4, 6, 8, … の要素を反転する
• 3回目の操作：位置3, 6, 9, 12, … の要素を反転する

つまり、i回目の操作では「iの倍数の位置にある要素」を反転（0→1、1→0）します。すべての操作を終えた後の配列に含まれる「1」の個数を数えましょう。

入力例と出力例

入力

Arr[] = { 0,0,0,0 }、N = 4

出力

N回の操作後の配列内の1の個数 ― 2

解説 ― 操作ごとの配列の状態は次のように変化します。

操作1: { 1,1,1,1 }
操作2: { 1,0,1,0 }
操作3: { 1,0,0,0 }
操作4: { 1,0,0,1 }

最終的な配列に含まれる「1」の個数は2です。

入力

Arr[] = { 0,0,0,0,0,0 }、N = 6

出力

N回の操作後の配列内の1の個数 ― 2

解説 ― 操作ごとの配列の状態は次のように変化します。

操作1: { 1,1,1,1,1,1 }
操作2: { 1,0,1,0,1,0 }
操作3: { 1,0,0,0,1,1 }
操作4: { 1,0,0,1,1,1 }
操作5: { 1,0,0,1,0,1 }
操作6: { 1,0,0,1,0,0 }

この場合も、最終的な配列に含まれる「1」の個数は2です。

アルゴリズムの考え方

• すべての要素を0で初期化した整数型配列Arr[]と整数Nを用意します。
• 関数Onecount()は、配列Arr[]とそのサイズNを引数として受け取り、N回の操作後の配列に含まれる「1」の個数を返します。
• 外側のforループはi=1から配列の末尾（N）まで繰り返し、各iが「i回目の操作」に対応します。
• 内側のforループも同様に配列の範囲を走査します。
• i回目の操作では、インデックスjがiの倍数（j % i == 0）である場合に、その位置の値を反転します。0なら1へ、1なら0へ切り替えます。
• この処理をすべてのiについて配列の末尾まで繰り返します。
• 注意：ループ変数はi=1、j=1から始まりますが、配列の添字は0〜N-1であるため、実際にはarr[j-1]を操作しています。
• 最後に配列全体をもう一度走査し、「1」の個数をcountに数えて返します。

C言語による実装例

#include <stdio.h>
int Onecount(int arr[], int N){
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            // jがiで割り切れる場合
            if (j % i == 0) {
                if (arr[j - 1] == 0)
                    arr[j - 1] = 1; // 0を1に反転
                else
                    arr[j - 1] = 0; // 1を0に反転
            }
        }
    }
    int count = 0;
    for (int i = 0; i < N; i++)
        if (arr[i] == 1)
            count++; // 1の個数をカウント
    return count;
}
int main(){
    int size = 6;
    int Arr[6] = { 0 };
    printf("Number of 1s in the array after N moves: %d", Onecount(Arr, size));
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Number of 1s in the array after N moves: 2

補足：計算量と数学的な性質

このシミュレーション手法の計算量はO(N log N)程度です。各i回目の操作では約N/i個の要素が反転されるためです。さらに、この問題には美しい数学的な性質があります。

位置kの要素は、「kの約数の個数」と同じ回数だけ反転されます。そして、約数の個数が奇数になるのはkが平方数である場合だけです。したがって、最終的に「1」が残るのは平方数の位置のみであり、答えは「N以下の平方数の個数」、すなわち⌊√N⌋となります。

例えば、N=4なら平方数は1と4の2個、N=6でも平方数は1と4の2個となり、どちらの出力例とも一致します。この性質を利用すれば、O(1)またはO(√N)という非常に効率的な方法で答えを求めることも可能です。