Make it Divisible solution codechef

Chef has an array AA of length NN.

Since Chef’s favorite number is 33, he wants to make all numbers in the array a multiple of 33.

Chef can do the following operation:

  • Select any 22 different indices ii and jj and increase AiAi by 11 and decrease AjAj by 11.

Help Chef find out the minimum number of operations required (or report its not possible) to achieve his objective.

Make it Divisible solution codechef – Input Format

 

November Cook-Off 2021 Division 3 - CodeChef

 

  • The first line will contain TT, the number of test cases. Then the test cases follow.
  • The first line of each test case contains NN, denoting the length of the array.
  • The second line of each testcase contains NN space separated integers AiAi.

Output Format

Output the minimum number of operations required to make all numbers divisible by 33.

If it is not possible to make every number divisible by 33, then output 1−1.

Make it Divisible solution codechef – Constraints

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 21052⋅105

Sample Input 1 

3
3
1 2 3
4
6 3 9 12
2
4 3

Sample Output 1 

1
0
-1

Explanation Make it Divisible solution codechef

Test Case 11: Chef can select the indices 22 and 11 and thus increase A2A2 by 11 and decrease A1A1 by 11. Thus the array becomes [0,3,3][0,3,3]. So every number is now divisible by 33.

Test Case 22: Since all the numbers are already multiples of 33, Chef will not need to apply the operation at all.

Test Case 33: There is no way to make all the numbers a multiple of 33.

Leave a Comment

Your email address will not be published. Required fields are marked *