Ninja And The Array

Easy

0/40

Average time to solve is 13m

Contributed by

0 upvote

Problem statement

Ninja has given an array 'A' of 'N' integers, each integer in an array is a power of 2. The ninja can perform the following operation on the array any number of times.

Choose any two equal integers from the array, remove them and insert their sum again in the array.

Ninja has to tell if after some moves (possibly zero or more) it is possible that number 2048 will exist in the array or not.

Return 1 if it is possible else return 0

EXAMPLE:

Input: 'N' = 4, 'A' = [1024, 512, 64, 512]

Output: 1

Remove integers at positions 2 and 4 and then push (512 + 512) at the end of an array.
Updated array will be 'A' = [1024, 64, 1024]
Remove integers at positions 1 and 3 and then push (1024 + 1024) at the end of an array.
Updated array will be 'A' = [64, 2048]

As the array contains integer 2048, the answer will be 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line will contain integer 'T' denoting the number of test cases. For each test case, the first line will contain a single integer 'N' the size of an input array, and the next line will contain 'N' integers denoting the array elements.

Output format :

For each test case, print a single line containing a boolean variable 1 if after some moves (possibly zero or more) it is possible that number 2048 will exist in the array else print 0.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^4
1 <= 'A[i]' <= 10^9
Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

1
0

Explanation Of Sample Input 1 :

For the first test case, as the array already contains the integer 2048 the answer will be 1.

For the second test case, as there are no two equal elements in an array, it is impossible to get the integer 2048. the answer will be 0.

Sample Input 2 :

2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048

Sample Output 2 :

0
1

Console