Number of Flips

Easy
0/40
134 upvotes
Asked in companies
Info Edge India (Naukri.com)WalmartD.E.Shaw

Problem statement

Ninja is learning the binary representation of the numbers. He wanted to practice the topic, so he picked a question. The problem statement says, two numbers, ‘A’ and ‘B’ are given. Find the number of bits of ‘B’ that should be flipped to convert it into ‘A’.Can you help Ninja to solve this problem?

You are given two integers, ‘A’ and ‘B’.Find the number of bits of ‘B’ that should be flipped to convert it into ‘A’.

For Example 
If ‘A’ is 13(1101) and ‘B’ is 7(0111), The number of bits that should be flipped is 2(0111).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘A’ and ‘B’.
Output Format: 
For each test case, print ‘an integer corresponding to the minimum number of swaps required.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= ‘A’,’B’ <= 10^9.

Time limit: 1 sec
Sample Input 1:
2
13 7
15 20
Sample Output 1:
2
4
Explanation of sample input 1:
For the first test case,

The binary representation of 13 is 1101.
The binary representation of 7 is 0111.
So, we will change the 2nd and the 4th bit from the right to convert B into A.
Hence, the answer is 2. 


For the second test case:

The binary representation of 20 is 10100.
The binary representation of 15 is 01111.
So, we will change the 1st,2nd,4th, and 5th bit from the right to convert B into A.
Hence, the answer is 4.
Sample Input 2:
2
3 10
6 4
Sample Output 2:
2
1
Hint

Check every bit of ‘A’ and ‘B’.

Approaches (2)
Brute Force.

In this approach, we will simply iterate through all the bits of ‘A’ and ‘B’ and count the number of bits that are not matching, as if we just change these mismatched bits, we will find the number of bits that should be flipped.

At last, we will return ‘ANS’ storing the number of flips required. 

 

Algorithm:

  • Declare ‘ANS’ to store the required answer.
  • While ‘A’ is greater than 0 or ‘B’ is greater than 0:
    • Set bit_A as A%2.
    • Set bit_B as B%2.
    • If bit_A is not equal to  bit_B:
      • Mismatched bit found.
      • Increase ‘ANS’ as ‘ANS’+1.
    • Set ‘A’ as ‘A’/2.
    • Set ‘B’ as ‘B’/2.
  • Return ‘ANS’.
Time Complexity

O(log(maximum of A and B)), where ‘A’ and ‘B’ are the given numbers.

 

In this approach, we traverse all the bits of ‘A’ and ‘B’.The number of bits of ‘A’ is of the order O(log(A)). Hence, the overall time complexity is O(log(maximum of A and B)).

Space Complexity

O(1).

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Number of Flips
Full screen
Console