Number of Bit Changes to Make Two Integers Equal

Easy
999.

Number of Bit Changes to Make Two Integers Equal

Number of Bit Changes to Make Two Integers Equal is an easy coding problem on bit manipulation, asked in Amazon, Google and Zoho interviews.

You may change any set bit of n to 0, as many times as you like, but you may never turn a 0 into a 1.

Return the number of changes needed to make n equal to k, or -1 if it cannot be done.

Example 1

Input
n = 13, k = 4
Output
2
Explanation
`13 = 1101` and `4 = 0100`; clear two bits.

Example 2

Input
n = 21, k = 21
Output
0
Explanation
Already equal.

Example 3

Input
n = 14, k = 13
Output
-1
Explanation
`13` needs bit 0 set, which `14` does not have.

Constraints

  • 1 <= n, k <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var minChanges = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Bit Changes to Make Two Integers Equal — Solution

Number of Bit Changes to Make Two Integers Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Bit Changes to Make Two Integers Equal is an easy coding problem on bit manipulation, asked in Amazon, Google and Zoho interviews.

  • Difficulty: Easy
  • Topics: Bit Manipulation
  • Asked at: Amazon, Google, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may change any set bit of n to 0, as many times as you like, but you may never turn a 0 into a 1.

Return the number of changes needed to make n equal to k, or -1 if it cannot be done.

Example 1

Input: n = 13, k = 4
Output: 2
Explanation: `13 = 1101` and `4 = 0100`; clear two bits.

Example 2

Input: n = 21, k = 21
Output: 0
Explanation: Already equal.

Example 3

Input: n = 14, k = 13
Output: -1
Explanation: `13` needs bit 0 set, which `14` does not have.

Constraints

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

Hints for Number of Bit Changes to Make Two Integers Equal

  1. Hint 1

    You can only clear bits, never set them.

  2. Hint 2

    So every bit of k must already be set in n.

  3. Hint 3

    When it is, the answer counts the bits n has that k does not.

How to solve Number of Bit Changes to Make Two Integers Equal

Clearing bits can only remove them, so k must be a submask of n — n & k == k. The number of changes is then the population count of n XOR k.

Approach

  1. Return -1 unless n & k == k.
  2. Count the set bits of n XOR k and return that.

Why it works

n & k == k is exactly the statement that every bit of k is present in n, which is the only way the restricted operation can reach k. Once that holds, n XOR k picks out precisely the bits that must be cleared — nothing else differs — so its population count is the answer.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Counting the differing bits without the submask check reports a number for impossible cases.
  • k > n is not the right test; the bits matter, not the magnitude.
  • Equal inputs answer 0, not 1.

Reference solution

Python

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

Java

public static int minChanges(int n, int k) {
    if ((n & k) != k) return -1;
    return Integer.bitCount(n ^ k);
}

C++

int minChanges(int n, int k) {
    if ((n & k) != k) return -1;
    return __builtin_popcount(n ^ k);
}

JavaScript

var minChanges = function(n, k) {
    if ((n & k) !== k) return -1;
    var diff = n ^ k;
    var count = 0;
    while (diff > 0) {
        count += diff & 1;
        diff = Math.floor(diff / 2);
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation