THREEPOW2 - Editorial

editorial
,
1

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.

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')
6 Likes
2

why So, if k=1 and the length of the string is ≥3the answer is Yes.

1 Like
3

Can anyone please explain the K=1 condition

4

@ary0804 @afzl210 if k = 1 then 2^x = 2^{x-1} + 2^{x-2} + 2^{x-2}. x - 2 \ge 0 implies x \ge 2 and length \ge 3.

6 Likes
5
  • If k > 3, then the answer is No; we have too many powers of 22 and can’t reduce them.
    why this is true? I tried to prove that during the contest but i couldn’t, when i saw many people solved it i took it like a fact but still i don’t know wht if you can explain it i would be thankful.
6

The number of set bits in the binary representation of a number n gives us the minimum number of powers of 2 which can be summed to n.
Example:
110 = 2^2 + 2^1
1011 = 2^3 + 2^1 + 2^0
So if k > 3, that would mean n can be only expressed as the sum of k or more powers of 2.

7

eg 8

9

thank you