【C++】配列の要素を増減する操作後に等しくできる最大要素数を求める方法

整数の配列が与えられたとき、以下の操作を繰り返し行った後に、配列内で等しくできる要素数の最大値を求める問題を考えます。

• i != j となる2つの要素 a[i] と a[j] を選ぶ
• a[i] を1増やし、a[j] を1減らす(a[i]++、a[j]--)

この操作では、1つの要素を増やして別の要素を減らすため、配列の合計値は常に一定であるという重要な性質があります。そこで、配列の合計値を要素数で割ることを考えます。配列のサイズを N とすると、次のように判定できます。

• 合計値が N で割り切れる場合:すべての要素を平均値に揃えられるため、等しくできる要素数は N
• 割り切れない場合:少なくとも1つの要素が他と異なる値になるため、最大でも N-1

入力例1

Arr[]= { 1,2,3 }

出力

等しい要素の最大数 : 3

説明 − 操作後、Arr[] = { 2,2,2 } となります(1を増やし、3を減らす)。要素の合計は 1+2+3=6 で、6%3==0 であるため、等しい要素数は3です。

入力例2

Arr[]= { 1,2,4 }

出力

等しい要素の最大数 : 2

説明 − 操作後、Arr[] = { 1,3,3 } となります(2を増やし、4を減らす)。要素の合計は 1+2+4=7 で、7%3==1 であるため、等しい要素数は 3-1=2 です。

アルゴリズムの考え方

• 整数配列 Arr[] に整数を格納します。
• 整数 'size' に配列の長さを格納します。
• 関数 maxEqual(int arr[], int n) は配列とそのサイズを引数として受け取り、操作適用後に配列内で等しくできる要素数の最大値を返します。
• まず、配列要素の合計を計算して 'sum' に格納します。
• 合計値がサイズ n で割り切れるかどうかを判定します(sum%n==0)。
• 割り切れる場合は n を返します。
• 割り切れない場合は n-1 を結果として返します。

このアルゴリズムの計算量は O(n) で、配列を一度走査して合計を求めるだけで判定できる非常に効率的な方法です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int maxEqual(int arr[], int n){
    int sum = 0;
    for (int i = 0; i < n; i++){
        sum += arr[i];
    }
    if (sum%n==0){
        return n;
    }
    return n-1;
}
int main(){
    int Arr[] = { 1, 4, 1, 2};
    // 配列のサイズ
    int size =4;
    cout <<" 等しい要素の最大数 :"<< maxEqual(Arr,size);
    return 0;
}

出力

等しい要素の最大数: 4

この例では、配列 { 1, 4, 1, 2 } の合計は 8 で、8%4==0 となるため、すべての要素を2に揃えることができ、答えは4となります。