# SINGLEOP2 - Editorial

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

TBD

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)