Watch 10 video solutions for Number of Bit Changes to Make Two Integers Equal, a easy level problem involving Bit Manipulation. This walkthrough by Developer Coder has 1,025 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |