Get started

Number of Bit Changes to Make Two Integers Equal — Easy Problem & Solution

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.

  • 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

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')

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 83 bit manipulation problems · the whole catalogue