Bailey is given a number in form of its binary representation S, having length N. Determine if the number can be represented as a sum of exactly three powers of 2. Please refer to samples for further explanation. Note that S will NOT contain leading zeros. Input Format The first line of input will contain a single integer T, denoting the number of test cases. Each test case consists of multiple lines of input. The first line of each test case contains a single integer N, the length of the binary string. The next line contains the string S, the binary representation of a number. Output Format For each test case, output YES if the number can be represented as sum of exactly three powers of 2.
Bailey is given a number in form of its binary representation S, having length N.
Determine if the number can be represented as a sum of exactly three powers of 2. Please refer to samples for further explanation.
Note that S will NOT contain leading zeros.
Input Format
- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N, the length of the binary string.
- The next line contains the string S, the binary representation of a number.
Output Format
For each test case, output YES if the number can be represented as sum of exactly three powers of 2.
Constraints
- 1≤T≤1000
- 1≤N≤2⋅105
- S consists of 0 and 1 only, and has no leading zeros.
- The sum of N over all test cases won't exceed 2⋅105.
Sample:
| INPUT | OUTPUT |
| 4 | NO |
| 1 | YES |
| 1 | YES |
| 4 | NO |
| 1001 | |
| 5 | |
| 11001 | |
| 7 | |
| 1101101 |
Explanation:
Test case 1: It is not possible to represent the given number as a sum of exactly three powers of 2.
Test case 2: The given string 1001 corresponds to the number 9. We can represent 9 as a sum of exactly three powers of 2 as 9=22+22+20.
Test case 3: The given string 11001 corresponds to the number 25. We can represent 25 as a sum of exactly three powers of 2 as 25=24+23+20.
Test case 4: It is not possible to represent the given number as a sum of exactly three powers of 2.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
