[Solution] Single Operation Part 1 solution codechef

Single Operation Part 1 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.

Table of Contents

[Solution] Single Operation Part 1 solution codechef

Chef wants to maximize the value of X after performing the operation. Help Chef in determining the value of Y which will maximize 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 containing the length of binary string S.
  • The second line of input contains the binary string S.

Output Format

For each test case, output on a new line, the value of Y which will maximize 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 1 solution codechef

Input

Output

4
2
10
2
11
3
101
3
110
1
2
1
2

[Solution] Single Operation Part 1 solution codechef Explanation:

Test case 1: Since S = 10 is the binary representation of 2, the current value of X = 2. On choosing Y = 1X becomes 2 \oplus \lfloor \frac{2}{2^{1}} \rfloor = 3. We can show that this is the maximum 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 = 2X becomes 3 \oplus \lfloor \frac{3}{2^{2}} \rfloor = 3. We can show that this is the maximum 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 = 1X becomes 5 \oplus \lfloor \frac{5}{2^{1}} \rfloor = 7. We can show that this is the maximum 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 = 2X becomes 6 \oplus \lfloor \frac{6}{2^{2}} \rfloor = 7. We can show that this is the maximum value of X we can achieve after one operation.

For Solution

“Click Here”

Leave a Comment