We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Bit Changes to Make Two Integers Equal

Number: 3508

Difficulty: Easy

Paid? No

Companies: ThoughtWorks

Problem Description

Given two positive integers n and k, you can change any bit in the binary representation of n that is 1 into 0. Your task is to determine the minimum number of such bit changes required to transform n into k. If it is impossible to do so, return -1.

Key Insights

  • Only allowed operation: change a 1 bit in n to 0.
  • It is impossible to transform n into k if k has a 1 bit at a position where n doesn’t.
  • The transformation is possible if and only if every bit set in k is also set in n.
  • The minimum number of operations required is the count of extra 1s in n that are not needed to represent k (i.e., count of 1s in n minus the count of 1s in k).

Space and Time Complexity

Time Complexity: O(1) – The algorithm performs a constant number of bit manipulation operations. Space Complexity: O(1) – Only a few extra integer variables are used.

Solution

To solve this problem, perform the following steps:

  1. Check if transformation is possible: verify that all bits set in k are also set in n. This can be checked using the condition (n & k) == k.
  2. If the condition fails, return -1 because it means k requires a 1 in a bit position where n has a 0.
  3. Otherwise, count the number of 1 bits in n and subtract the number of 1 bits in k. This difference gives the number of bit changes (1 to 0) required.
  4. Use bit manipulation operators to count bits efficiently.

Data Structures and Algorithmic Approach:

  • Use bitwise AND operations for checking compatibility.
  • Use bit counting techniques for computing the number of 1 bits in n and k.
  • The approach uses constant space and executes in constant time, making it both efficient and straightforward.

Code Solutions

# Python solution with detailed comments.
def number_of_bit_changes(n: int, k: int) -> int:
    # Check if every bit that is set in k is also set in n.
    # If any bit in k is not set in n, it's impossible to reach k (since we can only clear bits).
    if (n & k) != k:
        return -1

    # Count the number of 1-bits in n and k.
    # bin(x).count('1') converts the number to a binary string and counts '1's.
    count_n = bin(n).count('1')
    count_k = bin(k).count('1')
    
    # The number of changes required is the excess 1s in n that are not needed in k.
    return count_n - count_k

# Example usage
print(number_of_bit_changes(13, 4))  # Output: 2
print(number_of_bit_changes(21, 21)) # Output: 0
print(number_of_bit_changes(14, 13)) # Output: -1
← Back to All Questions