PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
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')