C++で配列の全要素を等しくするための最小操作回数を求めるアルゴリズム

問題の概要

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

例

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

解法の考え方

この問題のポイントは、「すでに同じ値になっている要素は操作する必要がない」という点に気づくことです。したがって、配列内で最も多く出現する値(最頻値)に他の要素をすべて揃えれば、操作回数を最小にできます。

アルゴリズムの手順

1. ハッシュマップを使って、各要素の出現回数を集計します。
2. 最大の出現回数(maxFrequency)を求めます。
3. 答えは「配列の長さ n − maxFrequency」となります。

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

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

出力

Minimum required operations = 3

計算量

• 時間計算量: O(n) — 配列を1回走査して各要素の頻度を集計し、その後ハッシュマップを走査して最大頻度を求めます。
• 空間計算量: O(n) — 最悪の場合(すべての要素が異なる値のとき)、ハッシュマップにn個のエントリが格納されます。

まとめ

この問題は「最頻値以外の要素だけを操作すればよい」というシンプルな発想で解けます。ハッシュマップによる頻度集計を活用することで、線形時間 O(n) で効率よく最小操作回数を求めることができます。