[Solution] Single Operation Part 2 CodeChef Solution

Problem

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.

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.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Explanation:

Test case $1$: Since $S = 10$ is the binary representation of $2$, the current value of $X = 2$. On choosing $Y = 2$, $X$ 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 = 1$, $X$ 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 = 2$, $X$ 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 = 1$, $X$ 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.