[Solution] Single Operation Part 2 solution codechef

Single Operation Part 2 solution codechef – Chef has the binary representation S of a number X with him. He can modify the number by applying the following operation exactly once:

• Make X := X \oplus \lfloor \frac{X}{2^{Y}} \rfloor, where (1 \leq Y \leq |S|) and \oplus denotes the bitwise XOR operation.

[Solution] Single Operation Part 2 solution codechef

Chef wants to minimize the value of X after performing the operation. Help Chef in determining the value of Y which will minimize the value of X after the operation.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of inputs:
• The first line contains the length of the binary string S.
• The second line contains the binary string S.

Output Format

For each test case, output on a new line, the value of Y which will minimize the value of X after the operation.

Constraints

• 1 \leq T \leq 5 \cdot 10^4
• 1 \leq |S| \leq 10^5
• The sum of |S| over all test cases won’t exceed 5 \cdot 10^5.
• S contains the characters 0 and 1 only.

[Solution] Single Operation Part 2 solution codechef

Input

Output

4
2
10
2
11
3
101
3
110

2
1
2
1


[Solution] Single Operation Part 2 solution codechef Explanation:

Test case 1: Since S = 10 is the binary representation of 2, the current value of X = 2. On choosing Y = 2X becomes 2 \oplus \lfloor \frac{2}{2^{2}} \rfloor = 2. We can show that this is the minimum value of X we can achieve after one operation.

Test case 2: Since S = 11 is the binary representation of 3, the current value of X = 3. On choosing Y = 1X becomes 3 \oplus \lfloor \frac{3}{2^{1}} \rfloor = 2. We can show that this is the minimum value of X we can achieve after one operation.

Test case 3: Since S = 101 is the binary representation of 5, the current value of X = 5. On choosing Y = 2X becomes 5 \oplus \lfloor \frac{5}{2^{2}} \rfloor = 4. We can show that this is the minimum value of X we can achieve after one operation.

Test case 4: Since S = 110 is the binary representation of 6, the current value of X = 6. On choosing Y = 1X becomes 6 \oplus \lfloor \frac{6}{2^{1}} \rfloor = 5. We can show that this is the minimum value of X we can achieve after one operation.