# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* utkarsh_25dec

*iceknight1093, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You’re given an integer represented by a binary string of length N.

Can it be represented as the sum of three powers of two?

# EXPLANATION:

First off, notice that N is quite large: so large that it’s impossible to directly convert it to an integer reasonably (in C/C++, at least).

This should hint towards the fact that we just need to work with the binary representation given to us.

The main observation that needs to be made here is that, for any m \gt 0, we have 2^m = 2^{m-1} + 2^{m-1}.

That is, we can split a single power of 2 into two powers of 2.

However, there’s no way to combine *distinct* powers of 2 into one; so essentially, we can only increase the number of powers of 2.

Now, suppose the string has k ones. This means the given integer is written as the sum of k distinct powers of 2; and by the property of the binary system, this k is *minimal*.

Let’s look at a few cases:

- If k \gt 3, then the answer is
`No`

; we have too many powers of 2 and can’t reduce them. - If k = 3, then the answer is clearly
`Yes`

; since the number is the sum of three distinct powers of 2. - If k = 2, then the answer is still
`Yes`

; split the larger power of 2 into two smaller ones. - If k = 1, then the answer is
`Yes`

sometimes. Notice that we need to split this power of 2 into three, so we need enough ‘space’ to do this (since the exponent will reduce by 2).- So, if k = 1 and the length of the string is \geq 3, the answer is
`Yes`

. - Otherwise, the answer is
`No`

.

- So, if k = 1 and the length of the string is \geq 3, the answer is

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Code (Python)

```
for _ in range(int(input())):
n = int(input())
s = input()
if s.count('1') == 2 or s.count('1') == 3 or (s.count('1') == 1 and n >= 3): print('Yes')
else: print('No')
```