C++で中央値をxに等しくするために追加が必要な最小の要素数を求める方法

問題の概要

サイズ n の配列 arr と要素 x が与えられたとき、配列の中央値が x と等しくなるようにするために、配列へ追加すべき要素の最小個数を求めるのがこの課題です。

ここで、長さ n の配列における中央値とは、要素を昇順（非減少順）にソートした際に (n-1)/2 番目の位置に存在する要素を指します。例えば、次の配列の場合、中央値は 20 となります。

arr1[] = {10, 20, 30, 40}

また、arr[] = {1, 2, 3}、x = 4 が与えられた場合を考えてみましょう。この場合、中央値を 4 にするためには {4, 5, 5, 5} の4つの要素を配列に追加する必要があります。

アルゴリズム

アルゴリズムの考え方は非常にシンプルです。配列の中央値が x と等しくなるまで、配列に x を1つずつ追加していきます。追加のたびに配列をソートし直し、中央値の位置にある要素が x になった時点での追加回数が答えとなります。

実装例

#include <iostream>
#include <algorithm>
using namespace std;
int minNumbersToBeAdded(int *arr, int n, int x){
    sort(arr, arr + n);
    int cnt = 0;
    while (arr[(n - 1)/2] != x) {
        arr[n] = x;
        ++n;
        sort(arr, arr + n);
        ++cnt;
    }
    return cnt;
}
int main(){
    int arr[20] = {1, 2, 3};
    int x = 4;
    int n = 3;
    cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
    return 0;
}

コードの解説

まず配列をソートし、現在の中央値 arr[(n-1)/2] が x と一致しているかどうかを判定します。一致していない場合は、配列の末尾に x を追加して要素数を1つ増やし、再度ソートして中央値を再計算します。この処理を中央値が x と一致するまで繰り返し、追加した回数をカウントして最終的な結果として返します。

なお、この実装では配列 arr を十分な大きさ（ここでは20要素分）で確保しておく必要があります。追加によって要素数が増えても、バッファの範囲を超えないように注意してください。

出力結果

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

Minimum numbers to be added = 4

この結果から、配列 {1, 2, 3} の中央値を 4 にするためには、最低4つの要素を追加する必要があることが分かります。