C++ですべての配列要素を等しくするために必要な最小操作回数を求める方法

問題文

n 個の正の整数からなる配列が与えられます。すべての要素を等しくするために必要な最小の操作回数を求めてください。1 回の操作では、配列内の任意の要素に対して、加算・乗算・減算・除算のいずれかを行うことができます。

例

入力配列が {1, 2, 3, 4} の場合、すべての要素を等しくするには最小で 3 回の操作が必要です。たとえば、要素 1 に対して 3 回の加算を行えば、すべての要素を 4 に揃えることができます。

アルゴリズム

1. 最も出現回数（頻度）が多い要素を選びます。これを「x」と呼びます。
2. 同じ値の要素がすでに x 個存在するため、残りの n − x 個の要素に対して操作を行えばよいことになります。したがって、必要な最小操作回数は n − x 回です。

このアプローチの計算量は、ハッシュマップを用いて各要素の頻度を数えるため、時間計算量 O(n)、空間計算量 O(n) となります。

実装例

#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 << "Minimum required operations = " <<
    getMinOperations(arr, n) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Minimum required operations = 3