C++で連続する偶数・奇数の配列から欠落している要素を見つける方法

問題の概要

連続する偶数を含む整数配列 even[] と、連続する奇数を含む整数配列 odd[] が与えられます。ただし、それぞれの配列から1つずつ要素が欠落しています。この記事では、その欠落している要素を効率的に求めるアルゴリズムとC++での実装方法を解説します。

入力例

even[] = {10, 8, 6, 16, 12}
odd[] = {3, 9, 13, 7, 11}

この場合、
偶数配列で欠落している数は「14」
奇数配列で欠落している数は「5」

アルゴリズム

この問題は、等差数列の和の公式を利用することで、配列を一度走査するだけで解くことができます。手順は以下の通りです。

• even[] 配列の中から最小値(minEven)と最大値(maxEven)を求めます。
• 最初のN個の偶数の和は「N × (N + 1)」という公式で表せます。これを使い、2からminEvenまでの偶数の和(sum1)、2からmaxEvenまでの偶数の和(sum2)をそれぞれ計算します。
• 完全な偶数配列の合計は reqSum = sum2 − sum1 + minEven となります。reqSum から実際の配列の合計を引けば、欠落している偶数が求まります。
• 同様に、最初のN個の奇数の和は「N²」であることを利用すれば、欠落している奇数も同じ考え方で求められます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

void findMissingNums(int even[], int sizeEven, int odd[], int sizeOdd) {
    int minEven = INT_MAX;
    int maxEven = INT_MIN;
    int minOdd = INT_MAX;
    int maxOdd = INT_MIN;
    int sumEvenArr = 0, sumOddArr = 0;

    // 偶数配列の最小値・最大値・合計を求める
    for (int i = 0; i < sizeEven; i++) {
        minEven = min(minEven, even[i]);
        maxEven = max(maxEven, even[i]);
        sumEvenArr += even[i];
    }

    // 奇数配列の最小値・最大値・合計を求める
    for (int i = 0; i < sizeOdd; i++) {
        minOdd = min(minOdd, odd[i]);
        maxOdd = max(maxOdd, odd[i]);
        sumOddArr += odd[i];
    }

    int totalTerms = 0, reqSum = 0;

    // 2〜minEven までの偶数の和(公式: N×(N+1))
    totalTerms = minEven / 2;
    int evenSumMin = totalTerms * (totalTerms + 1);

    // 2〜maxEven までの偶数の和
    totalTerms = maxEven / 2;
    int evenSumMax = totalTerms * (totalTerms + 1);

    // 理論上の合計 − 実際の合計 = 欠落した偶数
    reqSum = evenSumMax - evenSumMin + minEven;
    cout << "Missing even number = " << reqSum - sumEvenArr << "\n";

    // 2〜minOdd までの奇数の和(公式: N²)
    totalTerms = (minOdd / 2) + 1;
    int oddSumMin = totalTerms * totalTerms;

    // 2〜maxOdd までの奇数の和
    totalTerms = (maxOdd / 2) + 1;
    int oddSumMax = totalTerms * totalTerms;

    // 理論上の合計 − 実際の合計 = 欠落した奇数
    reqSum = oddSumMax - oddSumMin + minOdd;
    cout << "Missing odd number = " << reqSum - sumOddArr << "\n";
}

int main() {
    int even[] = {10, 8, 6, 16, 12};
    int sizeEven = sizeof(even) / sizeof(even[0]);
    int odd[] = {3, 9, 13, 7, 11};
    int sizeOdd = sizeof(odd) / sizeof(odd[0]);

    findMissingNums(even, sizeEven, odd, sizeOdd);
    return 0;
}

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

実行結果

Missing even number = 14
Missing odd number = 5

計算量について

この手法は各配列を一度走査するだけでよいため、時間計算量は O(N)、追加の記憶領域が不要で空間計算量は O(1) です。ソートを行って隣接要素を比較する方法やハッシュセットを使う方法と比べても、非常にシンプルかつ高速に動作するのが特徴です。