Conversion

Easy

0/40

Average time to solve is 20m

Contributed by

2 upvotes

Asked in companies

Problem statement

You are given two integers, ‘N’ and ‘M’. You are supposed to perform the following operation to convert ‘N’ to ‘M’.

In one operation, you can:

1. Choose any bit in ‘N’.

2. Flip the chosen bit, i.e., if the bit is ‘0’, make it ‘1’ and vice versa.

You are supposed to find the minimum number of operations needed to convert ‘N’ to ‘M’.

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 test cases follow.
The first line of each test case contains two integers, ‘N’ and ‘M’.

Output Format:

Print the minimum number of operations needed to convert from ‘N’ to ‘M’.
Print the output of each test case in a new line.

Constraints:

1<= T <= 10^4
0 <= N, M <= 10^9

Where ’T’ is the number of test cases and ‘N’,’M’ are the given integers.

Time Limit: 1 sec

Sample Input 1:

2
15 2
30 0

Sample Output 1:

3
4

Explanation for Sample Input 1:

In the first test case, the binary representation of ‘15’ is 1111, and the binary representation of ‘2’ is 0010, ie.
1111
0010
We can flip the third, first, and a fourth bit of 2 to convert 2 to 15. Hence, the answer is 3.

In the second test case, the binary representation of ‘30’ is 11110, and the binary representation of ‘0’ is 00000, ie.
11110
00000
We can flip the fourth, third, second, fifth bit of 0 to convert 0 to 30.

Sample Input 2:

2   
10 1
4 2

Sample Output 2:

3
2

Hint 1

Hint 2

Iterate through every bit of a number and check if they are the same or not.

Approaches (2)

Approach 1

Approach 2

Bruteforce

The idea is to iterate through each bit of the two numbers, and if at any position the bits of N and M are different, we will flip that bit in N.

Define a variable count and initialize it to 0. We will use this variable to count the number of bits we need to flip to make N equal to M.
Iterate through each bit of N and M,
- Check if the current bit is the same in N and M or not.
  1. If the bits are different, increment count by 1.
Return count.

Time Complexity

O(log(max(N,M))), where N and M are the given integers.

As we are iterating through each bit of N and M, there will be log(N) and log(M) bits in N and M, respectively. Hence the overall time complexity is O(log(max(N,M))).

Space Complexity

O(1), as we are using constant space.

(100% EXP penalty)

Conversion

Console