0〜99の範囲内で欠けている要素を見つけて出力する方法

このプログラムでは、ユーザーが入力した配列の中から、0〜99の範囲に存在しない値（欠落している要素）を検出して出力します。単一の欠落数値だけでなく、連続する欠落範囲（レンジ）も「開始値-終了値」の形式で表示できるのが特徴です。

入力例 : array = {88, 105, 3, 2, 200, 0, 10};
出力例 : 1 4-9 11-87 89-99

上記の例では、配列に含まれる 0〜99 の範囲の値は {88, 3, 2, 0, 10} だけです。105 と 200 は範囲外のため無視されます。その結果、存在しない 1、4〜9、11〜87、89〜99 が出力されます。

アルゴリズム

START
STEP 1-> 要素を持つ配列 array、すべて false で初期化した bool 型フラグ flag[MAX]、ループ用変数 i・j、配列サイズ n を用意する
STEP 2-> i を 0 から n 未満までインクリメントしながら繰り返す
    IF array[i] < 100 かつ array[i] >= 0
        flag[array[i]] = true を設定する
    End IF
STEP 3 -> For ループ終了
STEP 4 -> i を 0 から MAX 未満までインクリメントしながら繰り返す
    IF flag[i] == false
        j = i + 1 を設定する
        j < MAX かつ flag[j] == false の間、j++ を繰り返す
        IF j == i + 1
            i を出力する（単独の欠落数値）
        ELSE
            i と j-1 を出力する（欠落範囲）
        End IF
        i = j を設定し、次の範囲の先頭から再開する
End IF
STEP 5 -> For ループ終了
STOP

考え方のポイント

このアルゴリズムの核心はフラグ配列を使った存在チェックです。まず、0〜99 の範囲にある配列の要素に対応するフラグを true にします。これにより、最終的に false のまま残っているインデックスこそが「欠落している値」であることが分かります。続いて、false が連続している区間を調べることで、単一の欠落数値と連続的な欠落範囲を区別して出力しています。

計算量

• 時間計算量：O(n + MAX) — 配列の走査とフラグ配列の走査でそれぞれ線形時間
• 空間計算量：O(MAX) — フラグ配列のための追加メモリ

サンプルコード（C言語）

#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int main(int argc, char const *argv[]) {
    int array[] = {88, 105, 3, 2, 200, 0, 10};
    bool flag[MAX] = { false }; // すべてのフラグを false で初期化
    int i, j, n;
    n = sizeof(array)/sizeof(array[0]);
    for (i = 0; i < n; i++) {
        if (array[i] < 100 && array[i]>=0) {
            flag[array[i]] = true; // 配列に存在する値のフラグを true にする。true にならなかったものが欠落値
        }
    }
    for (i = 0; i < MAX; ++i) {
        if(flag[i] == false) { // false の値（＝欠落値）をチェック
            j = i+1; // 次の位置から調査を開始
            while(j<MAX && flag[j] == false) // flag[j] が false である限り継続
            j++;
            if (j==i+1) // 単独の欠落数値を出力
                printf("%d\n", i);
            else // 欠落範囲を出力
                printf("%d-%d\n", i, j-1);
            i = j; // 範囲の末尾の次の値から処理を再開
        }
    }
    return 0;
}

なお、C言語で bool 型を使用する場合は <stdbool.h> のインクルードが必要です（C99以降）。元のコードには含まれていませんでしたが、正しくコンパイルするために追加しています。

出力結果

上記のプログラムを実行すると、次のような出力が得られます。

1
4-9
11-87
89-99

各行は、配列に存在しなかった値または範囲を表しています。たとえば「4-9」は、4 から 9 までの 6 個の数値がすべて欠落していたことを意味します。この手法は、値の範囲が限定されている場合に非常に効率的で、ソート不要で欠落要素を検出できる点が大きなメリットです。