@Ansum: Notice that the problem does not ask to give a method of making as
many numbers as possible equal, but only what the maximum number is. Here
is an algorithm for achieving an array with the equality numbers I
specified:
1. If the sum of the numbers is a multiple of n, then avg = sum/n is the
target number. If every number is not equal to avg, find a number a[i] in
the array that is smaller than avg and a number a[j] that is larger than
avg. Then set a[i] = a[i]+1 and a[j] = a[j]-1. Repeat until every number
equals avg. Result is that n numbers are equal.
2. If the sum of the numbers is not a multiple of n, pick any number, say
a[1], as the target value. If there is any number a[k] from k = 2 to n-1
such that a[k] != a[1], increase or decrease a[k] by 1 to make it closer to
a[1] and respectively decrease or increase a[n] by 1. Repeat until every
number a[k] = a[1] for k = 2 to n-1. Then a[1] to a[n-1] are equal but a[n]
cannot be equal because then the sum of the numbers would be a multiple of
n. Result is that n-1 numbers are equal.
Since you don't have to produce the maximally equal array, the algorithm I
gave is the solution. Here it is in code (with C's 0-based array indexing):
int maxEqual( int n, int a[])
{
int i, sum = 0;
for( i = 0 ; i < n ; ++i )
sum += a[i];
return if sum % n == 0 ? n : n - 1;
}
Dave
On Thursday, November 22, 2012 1:25:43 AM UTC-6, Ansum Baid wrote:
> @Dave: Can you give a little insight on your approach?
>
> On Wed, Nov 21, 2012 at 6:52 PM, Dave <dave_an...@juno.com
> <javascript:>>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
>>>
>>>
>>> --
>>
>>
>>
>
>
--
