Given an array of positive integers, determine if it is possible to make all the elements in the array equal by adding non-negative number to its elements such that the sum of the added numbers is exactly M.

EXPLANATION:

For the given array A of size N, we want to determine whether it is possible to make all its elements equal by adding non-negative numbers to them. Let as assume that it is possible to do so and the final value of the elements is x.

This means the following two conditions must hold:

x >= A[i], for all i, and

sum of (x - A[i]) is M.

From the second condition, we can actually compute the value of x:
(x - A[1]) + (x - A[2]) + … + (x - A[N]) = M
x = (M + A[1] + A[2] + … + A[N]) / N

If x is not an integer, then clearly we do not have a solution. Hence, we need to check the following two conditions for the existence of a valid x:

(M + A[1] + A[2] + … + A[N]) must be divisible by N,

None of the elements of the array should exceed x = (M + A[1] + A[2] + … + A[N]) / N.

The x must hold : x>= max(A[i]) of the original array. So that all array elements become equal in the end.

Time Complexity:

O (N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

About this problem: my nephew chose this problem for me and I solved it in 8-9 minutes ACed solution. He was happy, and my approach was: take the sum of array, add m to it and if it’s divisible by N then Yes else No.
But I now know that it’s not correct. It should have showed WA, but it didn’t.

I took the sum of the heights of all the columns and M cubes and ultimately checked if the total sum was divisible by N (no. of columns) or not. My solution was accepted (my solution) but as stated by grebnesieh, the weak case i.e. when N=6, A=[1,12,12,12,12,12],M=5, the logic produces a ‘YES’ whereas it should produce a ‘NO’. So is it that the judge missed this case, is my code incorrect?

i found the max of array ,added value array elements A[i]-A[N] from M to equal max.
if M<0 it is a ‘NO’ if M=0 then it is ‘YES’.
if M > 0 ,dividing it by N print ‘YES’ if 0 or ‘NO’ if not.

this logic sounds pretty solid ,but it says wrong answer when submitted.

As I did, substract all elements of array from largest element and add the results of each substractions (Find least number of cubes of ground needed to make all columns in level). If sum is less than m then “No” and if equal to m then “Yes” and if greater than m then check whether (m - sum) is divisible by n or not. If divisible (level of each columns can be further increased by (m - sum)/n) then “Yes” otherwise “No”. http://www.codechef.com/viewsolution/4955148

As already stated, there were weak test cases for this problem. Some people haven’t checked for the second condition that final value of all elements should be greater than or equal to max element of the original array. E.g. for the first sample case:

5 7

3 3 4 2 1

We have sum=13, m=7 and n=5. So here, (sum+m)%n = 20%5 = 0 and hence some people report answer as ‘Yes’ which is incorrect.

If however we are given m=2 for above case, (sum+m)%n = 15%5 = 0 but still answer is ‘No’ because here (sum+m)/n = 15/5 = 3 is not greater than or equal to 4 (which was the max element in the array).

#include<stdio.h>
int main() {
int t, n, m, sum, highest, i, num, reqd;
scanf("%d", &t);
while (t-- > 0) {
highest = 0;
sum = 0;
i = 0;
scanf("%d%d", &n, &m);
while (i < n) {
scanf("%d", &num);
sum += num;
highest = (num > highest) ? num : highest;
i++;
}
reqd = (highest * n) - sum;
if (reqd > m) {
// If reqd number of blocks is more than available.
printf("NO\n");
} else if ((m - reqd) % n == 0) {
// If after making all columns equal to height of tallest column,
// remaining is equally distributable amongst them.
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}

I did it with the same logic, and now I have a question that even though you stated a weak case here, how come the judge accepted the solution? SERPLinker

Can anybody please tell what is the need for checking condition (m-sum) divisible by n? Why can’t we simply check the condition sum==m as we have to use EXACTLY m blocks. Plz help. Getting a WA.

First find the max of the array then find sum of how many each element of the array is short of max element…if this sum is greater than m then its false…otherwise check condition (m - sum) %n ==0
if it is true print yes else print false

For this case: N = 6, A = [1, 12, 12, 12, 12, 12], M = 5
sum(A) + M = 61 + 5 = 66.
Now 66 IS divisible by 6, so your solution would say “Yes” when clearly the answer is “No”. Unless I am missing something we got weak test-cases here.

@grebenesieh: I did it with the same logic, and now I have a question that even though you stated a weak case here, how come the judge accepted the solution?

Like I said, “weak test-cases”. Your code isn’t checked by some AI for correctness, it is just ran against a set of pre-defined inputs and if it gives the expected answer every time you get an accepted result. Clearly, the example I give above (or any variation of it) is not a part of their pre-defined inputs.