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 <= 106Problem Overview: Given two integers n and k, determine the minimum number of bit changes required to make them equal. The key constraint: you can only flip bits from 1 → 0. If k requires a bit that is 0 in n, the transformation is impossible.
Approach 1: Count Set Bit Differences (O(1) time, O(1) space)
This method compares the binary representation of both numbers using bitwise operations from bit manipulation. First check feasibility using (n & k) == k. This ensures every bit set in k is also set in n; otherwise you would need a 0 → 1 flip, which is not allowed. If the check passes, compute n ^ k to identify positions where bits differ. Every differing bit must be turned off in n. Count the set bits in this XOR result using a popcount operation. The number of set bits equals the required number of flips.
Approach 2: Direct Bit Count Comparison (O(1) time, O(1) space)
This version works directly at the bit level without relying entirely on XOR. Iterate through each bit position (usually up to 32 for standard integers) using shifts from bitwise operations. Extract the current bit of n and k with (x >> i) & 1. If a position has k = 1 but n = 0, the conversion cannot be done, so return -1. If n = 1 and k = 0, increment the change counter because that bit must be flipped off. Continue scanning all bit positions and return the total flips.
Both approaches rely on the same insight: only bits that are 1 in n but 0 in k need modification. Bit operations make the comparison extremely fast because integers have a fixed number of bits. These techniques are fundamental in problems involving masks, flags, and binary constraints, commonly grouped under bit manipulation.
Recommended for interviews: The XOR-based approach is usually expected. It shows strong familiarity with bitwise reasoning and produces a concise solution. The explicit bit iteration version is also acceptable and demonstrates understanding of how individual bits behave, but the XOR + popcount solution is shorter and more idiomatic.
To find the number of bit changes needed to make n equal to k, calculate the XOR of n and k. The result will give a number where each '1' represents a position where n and k differ. Count how many '1s' are present in the bits of n & ~k because you can only change 1s to 0s in n.
This C solution uses the process of counting differing bits using XOR. We first check if there are any bits in k that n does not cover; if so, we return -1 as the transformation is impossible. The while loop in combination with bit manipulation diff &= (diff - 1) counts how many bits differ from n to k.
Time Complexity: O(log n)
Space Complexity: O(1)
Count the number of '1' bits in the binary representation of n and k. If k has more '1s' than n, it is impossible to transform n into k as we can only change 1s to 0s. Otherwise, the number of changes required is simply the difference in their respective '1' counts.
This C implementation uses a helper function count_set_bits to determine the number of 1s in binary representation. The solution compares these counts for n and k to determine if the transformation is possible and, if so, the number of changes required.
Time Complexity: O(log n)
Space Complexity: O(1)
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 1s in the binary representation of n \oplus k.
The time complexity is O(log n), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Count Set Bit Differences | Time Complexity: O(log n) |
| Direct Bit Count Comparison | Time Complexity: O(log n) |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Set Bit Differences (XOR + Popcount) | O(1) | O(1) | Best general solution. Uses XOR to quickly identify differing bits and built-in bit counting. |
| Direct Bit Count Comparison | O(1) | O(1) | Useful when demonstrating manual bit inspection or when popcount utilities are unavailable. |
Number of Bit Changes to Make Two Integers Equal | Leetcode weekly-contest-407 | Java Solution • Developer Coder • 1,025 views views
Watch 9 more video solutions →Practice Number of Bit Changes to Make Two Integers Equal with our built-in code editor and test cases.
Practice on FleetCode