Flip Bits To Convert A To B

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given two numbers A and B.
2. You have to print the count of bits needed to be flipped to convert 'A' to 'B'.
Input Format
2 numbers A and B
Output Format
A number
Question Video
Constraints
-10^9 <= A,B <= 10^9
Sample Input
57
76
Sample Output
5


  • Editorial

    The problem here deals with calculating the number of bits that are needed to be flipped to convert an integer A to B. Flipping a bit means updating a bit with value 0 to 1 or to update a bit with value 1 to 0.

    For example:

    57 -> 0 1 1 1 0 0 1

    76 -> 1 0 0 1 1 0 0

    So we need to flip bits at positions 0, 1, 2, 4 and 6 (order is considered from left to right) to convert 57 to 76. Hence total 5 operations will be performed.

    The problem can be solved by taking the XOR of the two numbers, as we know that XOR gives a set bit at positions where there is an odd number of 1s, this is exactly what we desired, we need the positions that needed to be flipped and by performing XOR operation we achieved the task. Now all that is left is to count the number of set bits in the XOR integer by using Kerninghams algorithm to count the number of set bits.

    Time Complexity: O(k)

    The time complexity for the function is proportional to the number of set bits in the XOR integer.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name