Problem Description

You are given two positive integers n and k.

The problem allows you to perform a specific operation: you can select any bit in the binary representation of n that is currently 1 and change it to 0. You can perform this operation multiple times.

Your goal is to determine the minimum number of such changes needed to transform n into k. If it's impossible to achieve this transformation, you should return -1.

For example, if n = 13 (binary: 1101) and k = 4 (binary: 0100), you could change the bits at positions 0, 2, and 3 from 1 to 0, resulting in 0100 which equals k. This would require 3 changes.

The key constraint is that you can only change 1 bits to 0 bits - you cannot change 0 bits to 1 bits. This means if k has a 1 bit in any position where n has a 0 bit, the transformation is impossible.

The solution checks if n & k == k to verify that every 1 bit in k has a corresponding 1 bit in n. If this condition is met, the number of changes needed equals the count of 1 bits in n ^ k, which represents the positions where n and k differ.

Intuition

To understand this problem, let's think about what operations we can and cannot do. We can only change 1 bits to 0 bits in n, but we cannot change 0 bits to 1 bits.

This immediately gives us a critical insight: if k has a 1 bit at any position where n has a 0 bit, it's impossible to transform n into k. Why? Because we would need to change a 0 to a 1, which is not allowed.

How can we check this condition? By using the bitwise AND operation n & k. If n & k == k, it means that every 1 bit in k has a corresponding 1 bit in n. This is because AND operation only results in 1 when both bits are 1. If this condition fails, we return -1.

Once we know the transformation is possible, we need to count how many bits we need to change. These are the positions where n has a 1 but k has a 0.

The XOR operation n ^ k gives us exactly the positions where n and k differ - it results in 1 wherever the bits are different. Since we already know that all 1 bits in k exist in n, any difference must be a position where n has 1 and k has 0 - precisely the bits we need to change!

Therefore, counting the number of 1 bits in n ^ k gives us the minimum number of changes needed. The .bit_count() method efficiently counts these 1 bits, giving us our answer.

Solution Approach

The solution uses bit manipulation to efficiently solve this problem in a single line of code. Let's break down the implementation:

return -1 if n & k != k else (n ^ k).bit_count()

Step 1: Check if transformation is possible

First, we verify if the transformation from n to k is feasible using n & k != k:

• The bitwise AND operation n & k preserves only the bits that are 1 in both numbers
• If n & k == k, it means every 1 bit in k has a corresponding 1 bit in n
• If n & k != k, there's at least one position where k has 1 but n has 0, making transformation impossible
• In this case, we return -1

Step 2: Count the required changes

If transformation is possible, we calculate the number of changes using (n ^ k).bit_count():

• The XOR operation n ^ k produces a number where each bit is 1 if the corresponding bits in n and k are different
• Since we've already verified that all 1 bits in k exist in n, any difference must be where n has 1 and k has 0
• These are exactly the bits we need to change from 1 to 0
• The .bit_count() method counts the number of 1 bits in the XOR result, giving us the minimum number of changes needed

Time Complexity: O(1) - The bitwise operations and bit counting are constant time operations for integers within the typical range.

Space Complexity: O(1) - We only use a constant amount of extra space.

This elegant solution leverages the properties of bitwise operations to solve the problem without explicitly iterating through each bit position.

Example Walkthrough

Let's walk through the solution with n = 13 and k = 4.

Step 1: Convert to binary representation

• n = 13 → binary: 1101
• k = 4 → binary: 0100

Step 2: Check if transformation is possible using n & k == k

  1101 (n = 13)
& 0100 (k = 4)
-------
  0100 (result = 4)

Since n & k = 4 and k = 4, we have n & k == k, so transformation is possible!

This makes sense because the only 1 bit in k (at position 2) has a corresponding 1 bit in n.

Step 3: Count the bits that need to change using (n ^ k).bit_count()

  1101 (n = 13)
^ 0100 (k = 4)
-------
  1001 (result = 9)

The XOR gives us 1001, which has two 1 bits (at positions 0 and 3).

These represent:

• Position 0: n has 1, k has 0 → need to change
• Position 3: n has 1, k has 0 → need to change

Counting the 1 bits in 1001: 2 changes needed

Verification: Starting from 1101, if we change bits at positions 0 and 3 to 0:

• 1101 → 1100 (change position 0) → 0100 (change position 3)
• Final result: 0100 = 4 ✓

The answer is 2.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(log n). This is because:

• The bitwise AND operation n & k takes O(log n) time as it processes the binary representation of n bit by bit
• The XOR operation n ^ k also takes O(log n) time for the same reason
• The bit_count() method counts the number of set bits (1s) in the binary representation, which requires examining each bit position, taking O(log n) time

The space complexity is O(1). The algorithm only uses a constant amount of extra space for:

• Storing the result of n & k comparison
• Storing the result of n ^ k
• The internal counter for bit_count()

All operations are performed in-place without requiring additional space that scales with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Direction of Bit Changes

A common mistake is thinking you can change bits in both directions (0→1 and 1→0), leading to incorrect validation logic.

Incorrect approach:

def minChanges(self, n: int, k: int) -> int:
    # Wrong: This counts all differences without checking feasibility
    return (n ^ k).bit_count()

Why it fails: This doesn't check if transformation is possible. For example, with n = 4 (binary: 0100) and k = 7 (binary: 0111), this would return 2, but the transformation is actually impossible since we can't change 0s to 1s.

Correct approach:

def minChanges(self, n: int, k: int) -> int:
    # Must verify k's 1-bits are subset of n's 1-bits
    if n & k != k:
        return -1
    return (n ^ k).bit_count()

2. Using the Wrong Validation Condition

Some might check if n >= k thinking larger numbers have "more bits", but this is incorrect for binary operations.

Incorrect approach:

def minChanges(self, n: int, k: int) -> int:
    # Wrong: Numerical comparison doesn't ensure bit compatibility
    if n < k:
        return -1
    return (n ^ k).bit_count()

Why it fails: Consider n = 8 (binary: 1000) and k = 7 (binary: 0111). Here n > k, but transformation is impossible because k has 1s where n has 0s.

Correct validation: Always use n & k == k to ensure every 1-bit in k exists in n.

3. Manual Bit Counting Instead of Built-in Methods

Implementing custom bit counting can introduce bugs and inefficiency.

Error-prone approach:

def minChanges(self, n: int, k: int) -> int:
    if n & k != k:
        return -1
  
    # Manual counting - prone to errors
    xor_result = n ^ k
    count = 0
    while xor_result:
        count += 1
        xor_result &= xor_result - 1  # Clear rightmost bit
    return count

Better approach: Use Python's built-in bit_count() method which is both cleaner and less error-prone:

return (n ^ k).bit_count()

4. Confusing Bitwise AND with OR for Validation

Using OR instead of AND for checking bit compatibility is a subtle but critical error.

Incorrect approach:

def minChanges(self, n: int, k: int) -> int:
    # Wrong: OR doesn't verify subset relationship
    if n | k != n:
        return -1
    return (n ^ k).bit_count()

Why it fails: The condition n | k == n checks if k doesn't add any new 1-bits to n, but this is backwards - it would accept cases where k has 0s that we'd need to turn into 1s, which is impossible.

Remember: Use n & k == k to verify that k's bit pattern is achievable from n by only turning 1s to 0s.