Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

Alice and Bob recently studied bitwise operators and were extremely fascinated by them. Alice found the following function in a book :

Function magic(P, Q):

while Q > 0 :

A = P AND Q

B = P XOR Q

Q = A * 2

P = B

return P

Alice wondered how many times the while loop would run for any value of ‘P’ and ‘Q’. Alice gave Bob the binary representation of ‘P’ and ‘Q’ and asked him to help her count this.

Help Bob count the number of times the while loop would run for the given value of ‘P’ and ‘Q’.

Detailed explanation

```
1 <= T <= 10
1 <= |P|, |Q| <= 10^5
Sum of all |P| + |Q| overall test cases will not exceed 10^6.
Time Limit: 1 sec
```

```
2
110
10
1
1
```

```
3
2
```

```
In the first test case, initially ‘P’ is 6 and ‘Q’ is 2. After the first iteration, ‘P’ becomes 4 and ‘Q’ becomes 4. After the second iteration, ‘P’ becomes 0 and ‘Q’ becomes 8. After the third iteration, ‘P’ becomes 8 and ‘Q’ becomes 0.
In the second test case, initially ‘P’ is 1 and ‘Q’ is 1. After the first iteration, ‘P’ becomes 0 and ‘Q’ becomes 2. After the second iteration ‘P’ becomes 2 and ‘Q’ becomes 0.
```

```
2
1101
101
111
11101
```

```
3
4
```