C++で等比数列の欠けている数を見つける方法

等比数列の各項が順番に格納された配列があるとします。しかし、そのうちの1つの要素が欠けてしまっています。ここでの課題は、この欠けている要素を見つけることです。

例えば、arr = [1, 3, 27, 81] という配列が与えられた場合、本来は 9 が入るべき位置が空いているため、出力は 9 となります。

二分探索によるアプローチ

この問題は二分探索（バイナリサーチ）を使うことで効率的に解くことができます。基本的な考え方は以下の通りです。

• まず配列の中央要素（mid）に着目し、中央要素とその隣の要素との比が、数列の公比と一致しているかどうかを確認します。
• もし比が一致しなければ、欠けている要素は mid と mid + 1 のインデックスの間に存在することになります。
• 中央要素が等比数列の n/2 番目の位置として正しければ、欠けている要素は右半分にあります。そうでなければ左半分にあります。

この処理を再帰的に繰り返すことで、時間計算量 O(log n) で欠けている要素を特定できます。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;
class Progression {
    public:
    int missingUtil(int arr[], int left, int right, int ratio) {
        if (right <= left)
            return INT_MAX;
        int mid = left + (right - left) / 2;
        if (arr[mid + 1] - arr[mid] != ratio)
            return (arr[mid] * ratio);
        if (mid > 0 && arr[mid] / arr[mid - 1] != ratio)
            return (arr[mid - 1] * ratio);
        if (arr[mid] == arr[0] * pow(ratio, mid))
            return missingUtil(arr, mid + 1, right, ratio);
            return missingUtil(arr, left, mid - 1, ratio);
    }
    int missingElement(int arr[], int n) {
        int ratio = pow(arr[n-1]/arr[0], 1.0/n);
            return missingUtil(arr, 0, n - 1, ratio);
    }
};
int main() {
    Progression pg;
    int arr[] = {1, 3, 27, 81};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The missing element is: " << pg.missingElement(arr, n);
}

実行結果

The missing element is: 9

コードの解説

missingElement 関数では、最初の要素と最後の要素から公比を計算しています。pow(arr[n-1]/arr[0], 1.0/n) により、全体の比の n 乗根を求めることで公比を導き出します。

missingUtil 関数は再帰的に二分探索を行う本体です。中央要素と隣接要素の関係、および中央要素が理論値（arr[0] * pow(ratio, mid)）と一致するかどうかを判定し、探索範囲を半分ずつ絞り込んでいく仕組みです。