Last Updated: 21 Nov, 2021
Count the loop
Moderate
Asked in company
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’.
Input Format:
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.
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
Approaches
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].
- If it’s equal to 0 or 1 then it won’t affect the carrying process.
- If it’s equal to 2 then we either initiate the carrying process with ‘P[i]’ = ‘Q[i]’ = 1 or continue it with having carry = 1 and either ‘P[i]’ of ‘Q[i]’ being equal to 1.
- Finally, if it’s equal to 3 then the carrying process will start from scratch as after the first xor, there will be 0 on i-th place and carry will simply drop here, while some new carry from ‘P[i]’ + ‘Q[i]’ will go on (i + 1)th bit.
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:
- Initialise ‘ans’ to 0.
- If ‘Q[0]’ is ‘0’, return 0
- Reverse string ‘P’ and ‘Q’.
- Add ‘0’ to the end so that both their lengths become equal.
- Initialise ‘carry’ and ‘cn’ to 0.
- Run a loop ‘i’ from 0 to max length of the strings
- Update carry to carry + (P[i] - ‘0’) + (Q[i] - ‘0’)
- If ‘carry’ is equal to 2, increment ‘cn’ by 1.
- Else
- If ‘carry’ is less than or equal to 1, update ‘cn’ to 0.
- Else update ‘cn’ to 1.
- If ‘carry’ is less than or equal to 1, update ‘carry’ to 0.
- Else update ‘carry’ to 1.
- Update ‘ans’ to maximum of ‘ans’ and ‘cn’ + 1
- Return ‘ans’.