Number of Bit Changes to Make Two Integers Equal

Difficulty: Easy | Acceptance: 63.50% | Paid: No Topics: Bit Manipulation

You are given two positive integers n and k.

You are allowed to change n in the following way: choose any bit position of n and change the bit at that position from 0 to 1. You cannot change a bit from 1 to 0.

Return the minimum number of bit changes required to make n equal to k. If it is impossible, return -1.

• Examples
• Constraints
• Bit by Bit Comparison
• Bit Manipulation with XOR
• String Comparison

Examples

Input: n = 13, k = 10
Output: -1
Explanation: It is impossible to make n equal to k because we cannot change the 1 at position 1 to 0.

Input: n = 8, k = 13
Output: 2
Explanation: We can change the bits at positions 0 and 2 from 0 to 1 to make n equal to k.

Input: n = 1, k = 1
Output: 0
Explanation: n is already equal to k, no changes needed.

Constraints

1 <= n, k <= 10^9

Bit by Bit Comparison

Intuition Iterate through each bit position and check if we can transform n to k by only changing 0s to 1s.

Steps

• If n > k, return -1 (we can only increase value by changing 0s to 1s)
• For each bit position from 0 to 31:
  • If n has 1 and k has 0, return -1 (cannot change 1 to 0)
  • If n has 0 and k has 1, increment change count
• Return the total count of changes

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        if n > k:
            return -1
        
        changes = 0
        for i in range(32):
            n_bit = (n >> i) & 1
            k_bit = (k >> i) & 1
            if n_bit == 1 and k_bit == 0:
                return -1
            if n_bit == 0 and k_bit == 1:
                changes += 1
        
        return changes

Complexity

• Time: O(1) - fixed 32 iterations
• Space: O(1) - only using constant extra space
• Notes: Simple and straightforward approach

Bit Manipulation with XOR

Intuition Use bitwise operations to efficiently check validity and count required changes in one pass.

Steps

• If n > k, return -1
• Check if (n & k) == n - this ensures all 1s in n are also 1s in k
• If not equal, return -1 (impossible to transform)
• Count the number of 1s in (k ^ n) which represents bits that need changing

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        if n > k:
            return -1
        
        if (n & k) != n:
            return -1
        
        return bin(k ^ n).count('1')

Complexity

• Time: O(1) - constant number of bit operations
• Space: O(1) - only using constant extra space
• Notes: Most elegant solution using built-in bit counting functions

String Comparison

Intuition Convert numbers to binary strings and compare character by character for readability.

Steps

• If n > k, return -1
• Convert both numbers to binary strings
• Pad shorter string with leading zeros
• Compare each character pair:
  • If n has ‘1’ and k has ‘0’, return -1
  • If n has ‘0’ and k has ‘1’, increment count
• Return the total count

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        if n > k:
            return -1
        
        n_bin = bin(n)[2:]
        k_bin = bin(k)[2:]
        
        max_len = max(len(n_bin), len(k_bin))
        n_bin = n_bin.zfill(max_len)
        k_bin = k_bin.zfill(max_len)
        
        changes = 0
        for nb, kb in zip(n_bin, k_bin):
            if nb == '1' and kb == '0':
                return -1
            if nb == '0' and kb == '1':
                changes += 1
        
        return changes

Complexity

• Time: O(log n) - proportional to number of bits
• Space: O(log n) - for storing binary strings
• Notes: More readable but less efficient than bit manipulation