C++を使用して中央値をxに等しくするために追加する要素の最小数。

問題の説明

サイズnと要素xの配列「arr」が与えられた場合、タスクは、中央値がxに等しくなるように配列に追加される要素の最小数を見つけることです。

長さnの配列の中央値は、要素を降順ではない順序で並べ替えた後、位置番号（n-1）/2を占める要素です。たとえば、以下の配列の中央値は20-

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

arr [] ={1、2、3}およびx =4の場合、中央値を4に等しくするために、配列に4つの数値、つまり{4、5、5、5}を追加する必要があります

アルゴリズム

アルゴリズムは非常に単純です。配列の中央値が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;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum numbers to be added = 4