LeetCode 3226 - Number of Bit Changes to Make Two Integers Equal

The problem gives us two positive integers, n and k. We are allowed to perform one specific operation on n: choose any bit that is currently 1 in the binary representation of n and change it to 0.

leetcodeeasybit-manipulation

LeetCode Problem 3226

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem gives us two positive integers, n and k. We are allowed to perform one specific operation on n: choose any bit that is currently 1 in the binary representation of n and change it to 0.

We are not allowed to:

  • Change a 0 bit into 1
  • Change bits in k
  • Rearrange bits
  • Perform arithmetic operations

The task is to determine the minimum number of such bit changes required to transform n into k. If it is impossible, we return -1.

The key observation is that every operation only removes set bits from n. This means:

  • Every 1 bit in k must already exist as a 1 bit in n
  • If k contains a 1 in a position where n has 0, then it is impossible to construct k

For example:

  • n = 13 = 1101₂
  • k = 4 = 0100₂

We can turn off the extra 1 bits in n:

  • 1101 -> 0101
  • 0101 -> 0100

This requires 2 changes.

The constraints are very small:

  • 1 <= n, k <= 10^6

Since integers are at most around 20 bits wide, even a bit-by-bit simulation is extremely efficient. The problem is fundamentally a bit manipulation problem.

Important edge cases include:

  • n == k, where no operations are needed
  • k containing a 1 bit missing in n, making the transformation impossible
  • k = 0 is not possible because constraints guarantee positive integers, but intermediate results may become zero
  • Numbers with very different binary lengths, such as n = 1, k = 1024

Approaches

Brute Force Approach

A brute-force approach would simulate removing bits from n in every possible way until either:

  • We reach k
  • We exhaust all possibilities

This can be viewed as exploring subsets of the set bits in n. Since each set bit can either remain or be removed, the number of possible states is exponential in the number of set bits.

For every subset of bits:

  1. Construct the resulting number
  2. Check whether it equals k
  3. Count how many removed bits were needed

This works because every valid transformation corresponds to removing some subset of 1 bits from n.

However, this approach is unnecessary and inefficient because the problem structure gives us a direct bitwise condition.

Optimal Bit Manipulation Approach

The key insight is that transforming n into k is only possible if every 1 bit in k is already present in n.

In bitwise terms:

(k & n) == k

If this condition fails, then k requires a 1 bit that cannot be created, so the answer is -1.

If the transformation is possible, then the required operations are exactly the number of bits that are 1 in n but 0 in k.

Those are the bits we must turn off.

We can compute them using:

n ^ k

Since valid transformations guarantee that every differing bit is a 1 -> 0 transition, the number of operations is simply the number of set bits in n ^ k.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^b) O(1) Tries all subsets of set bits, where b is the number of set bits
Optimal O(log(max(n, k))) O(1) Checks bit validity and counts differing bits

Algorithm Walkthrough

  1. First, verify whether transforming n into k is even possible.

Since we can only turn 1 bits into 0, every 1 bit required by k must already exist in n.

We check this using:

(n & k) == k

If this condition is false, return -1. 2. Compute which bits differ between n and k.

The XOR operation identifies positions where the two numbers differ:

diff = n ^ k
  1. Count how many set bits exist in diff.

Each differing bit corresponds to one operation where a 1 in n must be turned into 0. 4. Return the count.

Why it works

The algorithm relies on the invariant that operations only remove set bits from n. Therefore, any bit set in k must already exist in n. Once this validity condition is satisfied, every remaining differing bit represents a removable extra 1 in n. Counting those bits gives the exact number of required operations.

Python Solution

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        # Impossible if k has a 1-bit where n has 0
        if (n & k) != k:
            return -1

        # Count differing bits
        return (n ^ k).bit_count()

The implementation begins with the feasibility check:

if (n & k) != k:

The bitwise AND keeps only bits present in both numbers. If the result is not equal to k, then k contains at least one 1 bit missing from n, making the transformation impossible.

Next, we compute:

n ^ k

The XOR operation marks every differing bit with 1. Because the feasibility check already guarantees that differences are only of type 1 -> 0, every set bit in the XOR result corresponds to one required operation.

Finally:

.bit_count()

counts how many operations are needed.

Go Solution

func minChanges(n int, k int) int {
    // Impossible if k has a 1-bit missing in n
    if (n & k) != k {
        return -1
    }

    diff := n ^ k
    count := 0

    for diff > 0 {
        count += diff & 1
        diff >>= 1
    }

    return count
}

The Go implementation follows the same logic as the Python version.

One difference is that Go does not provide a built-in bit_count() method for integers in the same simple form as Python. Instead, we manually count set bits by repeatedly checking the least significant bit and shifting right.

Because the constraints are small, this implementation is fully efficient.

Worked Examples

Example 1

Input:

n = 13
k = 4

Binary representations:

n = 1101
k = 0100

Step 1: Feasibility Check

Expression Result
n & k 1101 & 0100 = 0100
Compare with k 0100 == 0100

Transformation is possible.

Step 2: Compute Differences

Expression Result
n ^ k 1101 ^ 0100 = 1001

Step 3: Count Set Bits

Bit Position Value
3 1
2 0
1 0
0 1

Total set bits = 2.

Output:

2

Example 2

Input:

n = 21
k = 21

Binary:

10101
10101

Step 1: Feasibility Check

Expression Result
n & k 10101
Compare with k Equal

Step 2: XOR

Expression Result
n ^ k 00000

No differing bits exist.

Output:

0

Example 3

Input:

n = 14
k = 13

Binary:

n = 1110
k = 1101

Step 1: Feasibility Check

Expression Result
n & k 1110 & 1101 = 1100
Compare with k 1100 != 1101

k requires the last bit to be 1, but n has 0 there.

Transformation is impossible.

Output:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(log(max(n, k))) We process each bit at most once
Space O(1) Only a few integer variables are used

The number of bits in an integer grows logarithmically with its value. Since each bit is checked a constant number of times, the runtime is proportional to the bit length of the input numbers. The algorithm uses no auxiliary data structures, so the space complexity is constant.

Test Cases

sol = Solution()

# Provided examples
assert sol.minChanges(13, 4) == 2      # remove two bits
assert sol.minChanges(21, 21) == 0     # already equal
assert sol.minChanges(14, 13) == -1    # impossible transformation

# Simple removals
assert sol.minChanges(7, 3) == 1       # 111 -> 011
assert sol.minChanges(15, 0) == 4      # remove all bits

# Impossible cases
assert sol.minChanges(2, 3) == -1      # cannot create new bit
assert sol.minChanges(8, 1) == -1      # missing required bit

# Single-bit numbers
assert sol.minChanges(1, 1) == 0       # same number
assert sol.minChanges(1, 0) == 1       # remove only bit

# Larger values
assert sol.minChanges(1023, 511) == 1  # remove highest bit
assert sol.minChanges(1023, 0) == 10   # remove all ten bits

# Sparse bits
assert sol.minChanges(42, 40) == 1     # 101010 -> 101000

# Multiple removals
assert sol.minChanges(31, 16) == 4     # remove four bits

Test Case Summary

Test Why
13, 4 Standard valid transformation
21, 21 No changes needed
14, 13 Impossible due to missing bit
7, 3 Single bit removal
15, 0 Remove every set bit
2, 3 Cannot create new bits
8, 1 Missing required lower bit
1, 1 Smallest equal values
1, 0 Smallest removable case
1023, 511 Remove only highest bit
1023, 0 Stress all-bit removal
42, 40 Sparse binary representation
31, 16 Multiple removals required

Edge Cases

One important edge case occurs when n and k are already equal. In this situation, no operations are necessary, so the answer should be 0. A buggy implementation might incorrectly count bits or attempt unnecessary transformations. The XOR operation naturally handles this because n ^ k becomes zero, and the set bit count is zero.

Another critical edge case happens when k contains a 1 bit that does not exist in n. Since the operation only allows turning 1 into 0, it is impossible to create missing bits. For example, n = 8 and k = 1 fails because the least significant bit is absent in n. The feasibility check using (n & k) != k correctly detects this scenario immediately.

A third important edge case involves removing every set bit from n. For example, transforming 15 into 0 requires removing all four set bits. Some implementations incorrectly stop early or mishandle zero values after repeated shifts. The XOR-based counting method correctly handles this because every original set bit becomes part of the difference count.

A subtle edge case involves numbers with different binary lengths. For example, n = 1023 and k = 511. Here, only the highest bit differs, even though the numbers appear significantly different in decimal form. Bitwise operations naturally align binary positions correctly, ensuring the algorithm counts only truly differing bits.