Trong bài toán này, chúng ta được cung cấp một mảng arr có kích thước là n. Nhiệm vụ của chúng ta là Tìm số lượng các phép toán cần thiết để làm cho tất cả các phần tử của mảng bằng nhau
Phép toán được định nghĩa là phân phối các trọng số bằng nhau từ phần tử có trọng số tối đa cho tất cả các phần tử của mảng .
Nếu không thể làm cho các phần tử của mảng bằng nhau, hãy in -1.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {7, 3, 3, 3}
Output : 3 Giải thích
Mảng sau khi phân phối là {4, 4, 4, 4}
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm giá trị lớn nhất của mảng. Và sau đó sử dụng giá trị lớn nhất này để kiểm tra xem tất cả các phần tử của mảng có bằng nhau không và giá trị bằng phép trừ n (hoặc bội của nó) với giá trị lớn nhất của mảng. Nếu có, trả về n, nếu Không, trả về -1 (biểu thị là không thể).
Ví dụ
Hãy lấy một ví dụ để hiểu vấn đề
#include<bits/stdc++.h>
using namespace std;
int findOperationCount(int arr[],int n){
int j = 0, operations = 0;
int maxVal = arr[0];
int minVal = arr[0];
int maxValInd = 0;
for (int i = 1; i < n; i++){
if(arr[i] > maxVal){
maxVal = arr[i];
maxValInd = i;
}
if(arr[i] < minVal){
minVal = arr[i];
}
}
for (int i =0;i<n;i++){
if (arr[i] != maxVal && arr[i] <= minVal && arr[i] != 0){
arr[j] += 1;
arr[maxValInd] -= 1;
maxVal -= 1;
operations += 1;
j += 1;
}
else if (arr[i] != 0){
j += 1;
}
}
for (int i = 0; i < n; i++){
if (arr[i] != maxVal){
operations = -1;
break;
}
}
return operations;
}
int main(){
int arr[] = {4, 4, 8, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The number of operations required to make all array elements Equal is "<<findOperationCount(arr, n);
return 0;
} Đầu ra
The number of operations required to make all array elements Equal is 3