Flip Bits To Convert A To B
Try First, Check Solution later1. 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.Input Format
2. You have to print the count of bits needed to be flipped to convert 'A' to 'B'.
2 numbers A and BOutput Format
A numberQuestion Video
-10^9 <= A,B <= 10^9Sample Input
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.
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