SINGLEOP2 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Tejas Pandey
Tester: Harris Leung
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an integer X represented by a binary string S, in one move you can pick an integer 1 \leq Y \leq |S| and set X \gets X \oplus \left \lfloor \frac{X}{2^Y} \right \rfloor.

What is the minimum value of X that can be achieved after performing this exactly once?

EXPLANATION:

The idea used to solve this problem is essentially the same one as used in SINGLEOP1, so if you haven’t read that editorial you are encouraged to do so first.

In SINGLEOP1, we wanted to keep some prefix of 1's as-is and then flip the first zero we found.

In this problem, we want to minimize the result. To do that, we simply flip what we want to achieve: keep a prefix of 0's as-is, and flip the first 1 we find.
Note that the very first position cannot be changed, since we must choose Y \geq 1.

So,

  • Let a_1 be the position of the first occurrence (1-indexed) of a 1 in S, such that a_1 \geq 2
  • If a_1 does not exist, the string looks like 1000\ldots000, so the answer in this case is Y = |S|
  • Otherwise, the answer is Y = a_1 - 1.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = n
    for i in range(1, n):
        if s[i] == '1':
            ans = i
            break
    print(ans)