@Dave: Can you give a little insight on your approach? On Wed, Nov 21, 2012 at 6:52 PM, Dave <[email protected]> wrote:
> @Ansum: Polycarpus should start by summing the numbers. If the sum is > divisible by n, then n numbers can be made equal. If the sum is not > divisible by n, then only n-1 numbers can be made equal. > > Dave > > On Wednesday, November 21, 2012 12:18:54 PM UTC-6, Ansum Baid wrote: > >> This question has been taken from codeforces.com. Any idea how to solve >> this ? >> >> Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a** >> n*. Polycarpus likes it when numbers in an array match. That's why he >> wants the array to have as many equal numbers as possible. For that >> Polycarpus performs the following operation multiple times: >> >> >> - he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*); >> - he simultaneously increases number *a**i* by 1 and decreases number >> *a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j* = *a**j*- 1 >> . >> >> The given operation changes exactly two distinct array elements. >> Polycarpus can apply the described operation an infinite number of times. >> >> Now he wants to know what maximum number of equal array elements he can >> get if he performs an arbitrary number of such operation. Help Polycarpus. >> Input >> >> The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size. >> The second line contains space-separated integers *a*1, *a*2, ..., *a**n* >> (|*a**i*| ≤ 104) — the original array. >> Output >> >> Print a single integer — the maximum number of equal array elements he >> can get if he performs an arbitrary number of the given operation. >> Sample test(s) >> input >> >> 2 >> 2 1 >> >> output >> >> 1 >> >> input >> >> 3 >> 1 4 1 >> >> output >> >> 3 >> >> >> -- > > > --
