C++で要素を1つ追加して配列を等差数列に変換する方法

このチュートリアルでは、要素を1つ追加することで、与えられた配列を等差数列（算術数列）に変換するプログラムについて解説します。

ここでは、整数の配列が与えられます。私たちのタスクは、その配列に要素を1つだけ追加して等差数列へと変換し、追加した要素の値を返すことです。もし等差数列への変換が不可能な場合は、-1 を返します。

アルゴリズムの考え方

まず配列を昇順にソートし、最初の2つの要素の差を公差 d とします。その後、3番目以降の要素について、隣接する要素間の差を順番に確認していきます。

• すべての差が d と一致すれば、配列はすでに等差数列になっているため、末尾の要素に d を加えた値を返します。
• 差が 2d となっている箇所が1箇所だけあれば、そこに arr[i] - d の値を挿入することで等差数列にできます。
• 不整合が2箇所以上ある場合や、差が d でも 2d でもない場合は、変換は不可能なので -1 を返します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
// 追加すべき数値を返す関数
int print_number(int arr[], int n){
    sort(arr,arr+n);
    int d = arr[1] - arr[0];
    int numToAdd = -1;
    bool numAdded = false;
    for (int i = 2; i < n; i++) {
        int diff = arr[i] - arr[i - 1];
        if (diff != d) {
            if (numAdded)
                return -1;
            if (diff == 2 * d) {
                numToAdd = arr[i] - d;
                // 数値を追加済みの場合
                numAdded = true;
            }
            // 変換が不可能な場合
            else
            return -1;
        }
    }
    // 末尾の要素 + 公差を返す
    if (numToAdd == -1)
        return (arr[n - 1] + d);
    // 選択した数値を返す
    return numToAdd;
}
int main() {
    int arr[] = { 1, 3, 5, 7, 11, 13, 15 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << print_number(arr, n);
}

出力

9

コードの解説

上記の例では、配列 {1, 3, 5, 7, 11, 13, 15} が与えられています。ソート後の公差は d = 2 ですが、7 と 11 の間の差だけが 4（= 2d）となっています。そこで 9 を挿入すれば、{1, 3, 5, 7, 9, 11, 13, 15} という完全な等差数列になります。そのため、プログラムは追加すべき値として 9 を出力します。

このアルゴリズムの計算量は、ソートに O(n log n)、走査に O(n) となるため、全体の時間計算量は O(n log n) です。空間計算量は O(1) で、非常に効率的なアプローチと言えます。