You are given two positive integers n and k.
You can choose any bit in the binary representation of n that is equal to 1 and change it to 0.
Return the number of changes needed to make n equal to k. If it is impossible, return -1.
Example 1:
Input: n = 13, k = 4
Output: 2
Explanation:
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 = (0100)2 = k.
Example 2:
Input: n = 21, k = 21
Output: 0
Explanation:
n and k are already equal, so no changes are needed.
Example 3:
Input: n = 14, k = 13
Output: -1
Explanation:
It is not possible to make n equal to k.
Constraints:
1 <= n, k <= 106In #3226 Number of Bit Changes to Make Two Integers Equal, the goal is to determine how many bit changes are required to convert one integer into another under specific constraints. Since the problem involves comparing individual bits of two numbers, bit manipulation is the most efficient strategy.
A useful observation is that you only need to focus on positions where the bits differ. Using the XOR operation helps highlight these differing bits because it produces 1 wherever the two numbers have different values. However, before counting differences, you should ensure the transformation is valid based on the allowed bit operations. A quick bitwise check can determine whether the target number contains any bits that cannot be formed from the original number.
Once validity is confirmed, count the number of differing bits using a set-bit counting technique such as popcount. This results in a very efficient approach with O(log n) time (based on the number of bits) and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitwise Comparison with XOR and Set Bit Count | O(log n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Find the binary representations of <code>n</code> and <code>k</code>.
Any bit that is equal to 1 in <code>n</code> and equal to 0 in <code>k</code> needs to be changed.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
XOR highlights positions where two integers differ in their binary representation. Each set bit in the XOR result indicates a position where a change is required.
Bit manipulation problems like this are common in technical interviews at large tech companies. While this exact question may vary, the underlying concepts such as XOR and bit counting are frequently tested.
No special data structure is needed for this problem. Efficient bitwise operators and built-in bit counting functions are sufficient to compute the answer.
The optimal approach uses bit manipulation. First check if the transformation is valid using a bitwise condition, then use XOR to identify differing bits and count them with a popcount operation.