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 )
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
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
Hint

What does ‘A’ and ‘B’ represent in the algorithm?

Approaches (1)
Greedy


 

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’.

 


 

Time Complexity

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).


 

Space Complexity

O(1)


 

We are using constant extra space.


 

Code Solution
(100% EXP penalty)
Count the loop
Full screen
Console