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

Count the loop

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
2 upvotes
Asked in company
Intuit

Problem statement

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 ( Input/output format, Notes, Images )
Constraints:
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
Sample Input 1:
2 
110
10
1
1
Sample Output 1:
3
2
Explanation for Sample Input 1:
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.
Sample Input 2:
2
1101
101
111
11101
Sample Output 2:
3
4
Full screen
Console