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가 될 때까지 하나의 숫자 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