Maximum count of equal numbers in an array after performing given operations in C++

We are given with an array of integers. The goal is to find the maximum numbers in array that are equal after performing given operations −

• Select two elements a[i] and a[j] such that i != j and

• Increment a[i] and decrement a[j] ( a[i]++,a[j]-- )

We will take the sum of the array and divide it by the number of elements. If N is size of array then

If sum is divisible by N then equal numbers will also be N otherwise Equal numbers will be N-1.

Input

Arr[]= { 1,2,3 }

Output

Maximum count of equal numbers : 3

Explanation − After first step Arr[] = { 2,2,2 } increment 1 and decrement 3 Sum of elements is 1+2+3=6, 6%3==0, therefore equal numbers=3

Input

Arr[]= { 1,2,4 }

Output

Maximum count of equal numbers : 2

Explanation − After first step Arr[] = { 1,3,3 } increment 2 and decrement 4 Sum of elements is 1+2+4=7, 7%3==1, therefore equal numbers=3-1=2

Approach used in the below program is as follows

• The integer array Arr[] is used to store the integers.

• Integer ‘size’ stores the length of the array.

• Function maxEqual( int arr[], int n) takes an array , its size as input and returns the maximum count of equal numbers present in the array after applying a given operation.

• First of all we will calculate the sum of array elements and store in ‘sum’

• Now check divisibility of sum by size n (sum%n==0).

• If divisible then return n

• Else return n-1 as result.

Example

 Live Demo

#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};    // size of an array    int size =4;    cout <<" Maximum count of equal numbers :"<< maxEqual(Arr,size);    return 0; }

Output

Maximum count of equal numbers: 4