C++で2つの方程式を使って重複する数と欠落した数を見つける方法

この問題では、サイズNの配列arr[]が与えられます。配列には1からNまでの範囲の整数が含まれていますが、ある要素xが1つ欠落しており、その代わりに別の要素yが2回出現しています。私たちのタスクは、2つの方程式を立てて連立方程式を解くことで、重複している数と欠落している数を見つけることです。

問題の例

入力:

arr[] = {1, 2, 3, 3}

出力:

欠落している数 = 4、重複している数 = 3

解法のアプローチ

この問題は、欠落している数xと重複している数yについて2つの方程式を立て、それらを連立させて解くことで求められます。それぞれの方程式の導き方を見ていきましょう。

方程式1:合計の差から導く

まず、配列の要素の総和を考えます。1からNまでの自然数の和に対して、1つの要素(x)が抜け、別の要素(y)が余分に含まれているため、次の関係が成り立ちます。

arrSum = sum(N) − x + y
∴ y − x = arrSum − sum(N)

これが方程式1です。

方程式2:平方和の差から導く

次に、各要素の平方和についても同様に考えます。

arrSqSum = sqSum(N) − x2 + y2
∴ (y − x)(y + x) = arrSqSum − sqSum(N)

方程式1から「y − x」の値はすでにわかっているので、両辺を割ることで「x + y」が求まります。

x + y = (arrSqSum − sqSum(N)) / (arrSum − sum(N))

xとyを求める

方程式1と上記の結果を組み合わせると、次のようにyとxを算出できます。

y = {(arrSqSum − sqSum(N)) / (arrSum − sum(N)) + (arrSum − sum(N))} / 2
x = y − (arrSum − sum(N))

なお、計算に必要な公式は以下の通りです。

sum(N) = n × (n + 1) / 2
sqSum(N) = n × (n + 1) × (2n + 1) / 6

• arrSum: 配列の全要素の合計
• arrSqSum: 配列の全要素の平方の合計

C++での実装例

上記の解法を実装したプログラムが以下です。大きなNでもオーバーフローしないよう、中間計算にはlong long型を使用しています。

#include <iostream>
using namespace std;

void findMissingAndRepeatingVal(int arr[], int n) {
    long long sumN = (n * (n + 1)) / 2;
    long long sqSumN = (n * (n + 1) * (2 * n + 1)) / 6;
    long long arrSum = 0, arrSqSum = 0;

    for (int i = 0; i < n; i++) {
        arrSum += arr[i];
        arrSqSum += (long long)arr[i] * arr[i];
    }

    long long diff = arrSum - sumN;               // y − x
    long long sumXY = (arrSqSum - sqSumN) / diff; // x + y

    int y = (diff + sumXY) / 2;   // 重複している数
    int x = y - diff;             // 欠落している数

    cout << "配列に欠落している値は " << x;
    cout << "\n配列に2回現れる値は " << y;
}

int main() {
    int arr[] = { 1, 2, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findMissingAndRepeatingVal(arr, n);
    return 0;
}

出力

配列に欠落している値は 5
配列に2回現れる値は 2

計算量

時間計算量: O(N) ― 配列を一度走査するだけで済みます。
空間計算量: O(1) ― 追加のメモリは不要です。