#3226

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Number of Bit Changes to Make Two Integers Equal

Find the number of bit changes to make two integers equal using bit manipulation techniques.

Problem Statement

You are given two positive integers, n and k. You can select any bit in the binary representation of n that is equal to 1 and change it to 0.

Return the number of changes required to make n equal to k. If it is impossible to convert n into k, return -1.

Examples

Example 1

Input: n = 13, k = 4

Output: 2

Initially, the binary representations of n and k are n = (1101) 2 and k = (0100) 2 . We can change the first and fourth bits of n . The resulting integer is n = ( 0 10 0 ) 2 = k .

Example 2

Input: n = 21, k = 21

Output: 0

n and k are already equal, so no changes are needed.

Example 3

Input: n = 14, k = 13

Output: -1

It is not possible to make n equal to k .

Constraints

1 <= n, k <= 106

Solution Approach

Binary Representation Comparison

The primary approach is to convert both integers, n and k, into their binary representations. Then, check for mismatched bits. For every bit in n that needs to be flipped to match k, count it as a required change. This solution hinges on the idea that bits set to 1 in n should match the corresponding bits in k.

Bitwise Operations

Use XOR (^) to find the positions of differing bits between n and k. Each differing bit corresponds to a necessary change. XOR is efficient for identifying bit differences, and this approach minimizes complexity.

Handling Impossibility

Before counting the changes, ensure that k does not have any bits set where n has corresponding zeroes. If such positions exist, return -1, as it is impossible to flip bits from 0 to 1 using the problem's rules.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of bits in the integers. Converting both integers to binary takes linear time relative to their size. The XOR operation also runs in linear time, so overall, the solution runs in O(log n) time. The space complexity is constant, O(1), since only a fixed amount of extra space is required to store intermediate results.

What Interviewers Usually Probe

Look for candidates who understand bit manipulation concepts like XOR and bit shifts.
Evaluate how well the candidate can translate bitwise operations into a solution strategy.
Assess the candidate’s understanding of edge cases, like impossibilities in the transformation of n to k.

Common Pitfalls or Variants

Common pitfalls

Forgetting that bits in k set to 1 when corresponding bits in n are 0 make the problem unsolvable.
Incorrectly assuming that the binary representation comparison only requires a one-to-one match, overlooking the transformation rules.
Misunderstanding the XOR operation and not using it to efficiently detect bit differences.

Follow-up variants

Extend this problem to include multiple integers and find the minimum number of changes to make all integers equal.
Consider a variant where bits can be flipped both ways (0 to 1 and 1 to 0) to make n equal to k.
Introduce a time limit constraint for large inputs and test the efficiency of the solution.

FAQ

What is the main strategy to solve 'Number of Bit Changes to Make Two Integers Equal'?

The main strategy is to compare the binary representations of the two integers, using bitwise operations like XOR to identify the positions that need to be changed.

What happens if it is impossible to make the integers equal?

If it is impossible to change n into k (when k has bits set to 1 where n has 0s), the answer should be -1.

How do XOR operations help in solving this problem?

XOR helps by efficiently identifying the positions where the bits differ between n and k, allowing you to count how many bits need to be flipped.

What are the time and space complexities of the solution?

The time complexity is O(log n) due to the binary representation and XOR operations. The space complexity is O(1) as it only requires a fixed amount of extra space.

Can this problem be extended to multiple integers?

Yes, one variant could involve extending the problem to multiple integers, where you calculate the minimum number of bit changes required to make all integers equal.

terminal

Solution

Solution 1: Bit Manipulation

If the bitwise AND result of $n$ and $k$ is not equal to $k$, it indicates that there exists at least one bit where $k$ is $1$ and the corresponding bit in $n$ is $0$. In this case, it is impossible to modify a bit in $n$ to make $n$ equal to $k$, and we return $-1$. Otherwise, we count the number of $1$s in the binary representation of $n \oplus k$.

1

2

3

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        return -1 if n & k != k else (n ^ k).bit_count()

Continue Practicing

#3211 generate binary strings without adjacent zeros #3209 number of subarrays with and value of k #3191 minimum operations to make binary array elements equal to one i