Số phần tử tối thiểu cần thêm để tạo giá trị trung vị bằng x bằng cách sử dụng C ++.

Tuyên bố vấn đề

Cho một mảng “arr” có kích thước n và phần tử x, nhiệm vụ là tìm số phần tử tối thiểu được thêm vào trong mảng để làm cho giá trị trung bình bằng x.

Trung vị trong một mảng có độ dài n là một phần tử chiếm vị trí số (n-1) / 2 sau khi chúng ta sắp xếp các phần tử theo thứ tự không giảm. Ví dụ:trong mảng bên dưới trung vị là 20 -

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

Nếu arr [] ={1, 2, 3} và x =4 thì chúng ta phải thêm 4 số, tức là {4, 5, 5, 5} trong mảng để tạo số trung vị bằng 4

Thuật toán

Thuật toán rất đơn giản. Chúng ta phải thêm một số x vào mảng cho đến khi giá trị trung bình của mảng bằng x

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum numbers to be added = 4