@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 > > > --