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’.
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains one binary string, ‘P’ denoting the binary representation of the first number.
The following line contains one binary string, ‘Q’, denoting the binary representation of the second number.
Output Format:
For each test case, print a single integer denoting the number of times the while loop will run.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
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
What does ‘A’ and ‘B’ represent in the algorithm?
Note that, ‘B’ represents digiti-wise sum and ‘A’ represents carry. For example, let’s say an index ‘i’ of ‘P’ is ‘1’ and that for ‘Q’ is ‘1’, then ‘B[i]’ will store ‘0’ and ‘A[i]’ will store ‘1’ which is the digit-wise sum and carry.
We may interpret the whole process as if we simultaneously started addition in all points and carried excessive bits in all places at the same time. The final answer will be the length of the longest carry chain.
We can get the whole time of the process by some case-work.Notice the following for ‘P[i]’ + ‘Q[i]’ + carry[i].
Thus, the answer to the problem can be obtained by carefully simulating the process. You should also take an extra look at the B = 0 case.
For example, if ‘P’ = 1 and ‘Q’ = 1, after 1st iteration ‘P’ will become 0 and ‘Q’ will become ‘10’. After the second iteration, both ‘P’ and ‘Q’ will become 0, so answer for this will be 2.
Algorithm:
O(N), where ‘N’ is the length of the longer string.
Since we are iterating through the string once, the time complexity is O(N).
O(1)
We are using constant extra space.