Tuyên bố vấn đề
Cho một mảng với n số nguyên dương. Chúng ta cần tìm số phép toán tối thiểu để làm cho tất cả các phần tử bằng nhau. Chúng ta có thể thực hiện cộng, nhân, trừ hoặc chia với bất kỳ phần tử nào trên một phần tử mảng.
Ví dụ
Nếu mảng đầu vào là ={1, 2, 3, 4} thì chúng ta yêu cầu 3 phép toán tối thiểu để làm cho tất cả các phần tử bằng nhau. Ví dụ:chúng ta có thể tạo phần tử 4 bằng cách thực hiện 3 phép cộng.
Thuật toán
1. Select element with maximum frequency. Let us call it ‘x’ 2. Now we have to perform n-x operations as there are x element with same value
Ví dụ
#include
using namespace std;
int getMinOperations(int *arr, int n) {
unordered_map hash;
for (int i = 0;i < n; ++i) {
hash[arr[i]]++;
}
int maxFrequency = 0;
for (auto elem : hash) {
if (elem.second > maxFrequency) {
maxFrequency = elem.second;
}
}
return (n - maxFrequency);
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum required operations = " <<
getMinOperations(arr, n) << endl;
return 0;
} 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
Đầu ra
Minimum required operations = 3