Số phép toán tối thiểu làm tất cả phần tử mảng bằng nhau trong C++

Đề bài

Cho mảng n số nguyên dương. 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. Có thể thực hiện phép cộng, nhân, trừ, chia với bất kỳ phần tử nào trên phần tử mảng.

Ví dụ

Nếu mảng đầu vào = {1, 2, 3, 4} thì cần tối thiểu 3 phép toán để làm tất cả phần tử bằng nhau. Ví dụ, có thể làm phần tử thành 4 bằng 3 phép cộng.

Thuật toán

1. Chọn phần tử có tần suất lớn nhất. Gọi nó là 'x'.
2. Bây giờ phải thực hiện n-x phép toán vì có x phần tử cùng giá trị.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

int getMinOperations(int *arr, int n) {
    unordered_map<int, int> 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 << "Số phép toán tối thiểu = " << getMinOperations(arr, n) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số phép toán tối thiểu = 3