Скачать или смотреть Single Operation Part 2 - Codechef October Long 2022 (Code + Explanation for beginners)

#codechefoctoberlong2022 #singleperationpart2 #singleop2


SINGLEOP2

Problem

Chef has the binary representation SS of a number XX with him. He can modify the number by applying the following operation exactly once:

Make X := X \oplus \lfloor \frac{X}{2^{Y}} \rfloorX:=X⊕⌊2YX​⌋, where (1 \leq Y \leq |S|)(1≤Y≤∣S∣) and \oplus⊕ denotes the bitwise XOR operation.

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

Input Format

The first line of input will contain a single integer TT, 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 SS.

The second line contains the binary string SS.

Output Format

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

Constraints

1 \leq T \leq 5 \cdot 10^41≤T≤5⋅104

1 \leq |S| \leq 10^51≤∣S∣≤105

The sum of |S|∣S∣ over all test cases won't exceed 5 \cdot 10^55⋅105.

SS contains the characters 00 and 11 only.

Sample 1:

Input

Output

4 2 10 2 11 3 101 3 110

2 1 2 1

Explanation:

Test case 11: Since S = 10S=10 is the binary representation of 22, the current value of X = 2X=2. On choosing Y = 2Y=2, XX becomes 2 \oplus \lfloor \frac{2}{2^{2}} \rfloor = 22⊕⌊222​⌋=2. We can show that this is the minimum value of XX we can achieve after one operation.
Test case 22: Since S = 11S=11 is the binary representation of 33, the current value of X = 3X=3. On choosing Y = 1Y=1, XX becomes 3 \oplus \lfloor \frac{3}{2^{1}} \rfloor = 23⊕⌊213​⌋=2. We can show that this is the minimum value of XX we can achieve after one operation.
Test case 33: Since S = 101S=101 is the binary representation of 55, the current value of X = 5