# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Tejas Pandey

*Harris Leung*

**Tester:***Nishank Suresh*

**Editorialist:**# 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)
```