Make them Zero solution codechef

Make them Zero solution codechef

You are given an array AA of length NN.

You can perform the following operation on the array any number of times:

  • Choose any subsequence SS of the array AA and a positive integer XX such that XX is a power of 22 and subtract XX from all the elements of the subsequence SS.

Find the minimum number of operations required to make all the elements of the array equal to 00.

Input Format

  • First line will contain TT, number of test cases. Then the test cases follow.
  • First line of each test case contains an integer NN denoting the length of the array AA.
  • Second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN – denoting the elements of array AA.

Output Format

For each test case, output in a single line, the minimum number of moves required to make all the elements of the array AA equal to 00.

Make them Zero solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • 0Ai1090≤Ai≤109
  • Sum of NN over all test cases do not exceed 21052⋅105.
  • Through this contest, selected students get access to a free 6 month LinkedIn Premium subscription which helps students:
    • Discover & apply to 20M+ jobs/internships on LinkedIn
    • Reach out to hiring managers/recruiters/mentors directly
    • Find career paths that people similar to them have taken
    • Learn from over 17K expert-led LinkedIn Learning courses (technical & soft-skills) with certificates

Sample Input 1 

4
3
2 2 2
4
2 2 2 4
2
0 0
3
1 2 3

Sample Output 1

Make them Zero solution codechef

1
2
0
2

Make them Zero solution codechef

Test Case 11: Take the subsequence with indices {1,2,3}{1,2,3} and subtract 21=221=2 from each element.

Test Case 22: Take the subsequence with indices {1,2,3,4}{1,2,3,4} and subtract 21=221=2 from each element. After this operation, the array becomes [0,0,0,2][0,0,0,2]. Now, take the subsequence with index {4}{4} and subtract 21=221=2 from it.

Test Case 33: All the elements are already 00.

Test Case 44: Take the subsequence with indices {2,3}{2,3} and subtract 21=221=2 from it. Now, the array becomes [1,0,1][1,0,1]. Now, take the subsequence with indices {1,3}{1,3} and subtract 20=120=1 from it.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.