maximum no of equal elements in the array after n transformation [closed]

Question

You have an array containing n elements. At any move, you choose two indices i and j, i not equals j and increment value at one index and decrease value at other index. You can make this move any number of times. We need is the maximum number of elements which can have the same value (after any number of moves). Example for 1,2,3,4 answer is 3 since we can have at most 3 elements equal after applying the moves any number of times. But i am searching for the algorithm to do that so needed help.

Answer 1

As stated, this doesn't take much of an algorithm. If you can do it as many times as you want, you should always be able to get a result with either N or N-1 elements equal (where N is the size of the input array).

Take the sum of the input. For example, in your case: sum(1,2,3,4) = 10.

If sum % N == 0, the answer is N. Any time before that, you'll have at least one element higher than sum/N and at least one lower. Increment the low, decrement the high.

Else the answer is N-1. The final set can have N-1 elements equal to (int)sum/N and the last element will be the remainder from the original sum. You can use that last element as a "spare" to increment/decrement whichever other elements you want.

Since you don't have to actually find the transformations, the end result is O(N). You just take the sum and mod it by N to check which answer to give. There's no use recursing or searching for "averaging pairs" unless you want to find the sequence of steps that lead to the answer..