Number of Bit Changes to Make Two Integers Equal - Solution & Explanation
Problem Statement
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 <= 106
Approach Overview
Problem 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.
Approach 1: Count Set Bit Differences
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.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Direct Bit Count Comparison
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.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 3: 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 1s in the binary representation of n \oplus k.
The time complexity is O(log n), and the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Count Set Bit Differences | Time Complexity: O(log n) |
| Direct Bit Count Comparison | Time Complexity: O(log n) |
| Bit Manipulation | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Number of Bit Changes to Make Two Integers Equal | Leetcode weekly-contest-407 | Java Solution • Developer Coder • 1,030 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Bit Changes to Make Two Integers Equal easy or hard?
Number of Bit Changes to Make Two Integers Equal Python/Java solution
How to solve Number of Bit Changes to Make Two Integers Equal in O(1)?
What is the best approach for Number of Bit Changes to Make Two Integers Equal?
Is Number of Bit Changes to Make Two Integers Equal asked at Google/Amazon/Meta?
What data structure is used in Number of Bit Changes to Make Two Integers Equal?
What is the time complexity of Number of Bit Changes to Make Two Integers Equal?
Ready to solve this problem?
Practice Number of Bit Changes to Make Two Integers Equal with our built-in code editor and test cases.
Practice on FleetCode