problemeasyalgorithmsleetcode-3226leetcode 3226leetcode3226

Number of Bit Changes to Make Two Integers Equal

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

You are given two positive integers n and k.

You can choose any bit in the binary representation of n that is equal to 1 and change it to 0.

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

Examples

Example 1


Input: n = 13, k = 4

Output: 2

Explanation:  
Initially, the binary representations of `n` and `k` are `n = (1101)2` and `k
= (0100)2`.  
We can change the first and fourth bits of `n`. The resulting integer is `n =
(_**0**_ 10 _**0**_)2 = k`.

Example 2


Input: n = 21, k = 21

Output: 0

Explanation:  
`n` and `k` are already equal, so no changes are needed.

Example 3


Input: n = 14, k = 13

Output: -1

Explanation:  
It is not possible to make `n` equal to `k`.

Constraints

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

Solution

Method 1 – Bit Manipulation and Subset Check

Intuition

You can only turn 1s in n to 0s, so k must be a subset of n (all 1s in k must be present in n). The answer is the number of 1s in n that are not in k.

Approach

  1. If (n | k) != n, return -1 (k has 1s where n has 0s).
  2. Count the number of 1s in n that are not in k (i.e., in n & ~k).
  3. Return the count.

Code

C++
class Solution {
public:
    int minBitChanges(int n, int k) {
        if ((n | k) != n) return -1;
        int diff = n & ~k, cnt = 0;
        while (diff) { cnt += diff&1; diff >>= 1; }
        return cnt;
    }
};
Go
func minBitChanges(n, k int) int {
    if n|k != n { return -1 }
    diff, cnt := n&^k, 0
    for diff > 0 { cnt += diff&1; diff >>= 1 }
    return cnt
}
Java
class Solution {
    public int minBitChanges(int n, int k) {
        if ((n | k) != n) return -1;
        int diff = n & ~k, cnt = 0;
        while (diff > 0) { cnt += diff&1; diff >>= 1; }
        return cnt;
    }
}
Kotlin
class Solution {
    fun minBitChanges(n: Int, k: Int): Int {
        if ((n or k) != n) return -1
        var diff = n and k.inv(); var cnt = 0
        while (diff > 0) { cnt += diff and 1; diff = diff shr 1 }
        return cnt
    }
}
Python
class Solution:
    def minBitChanges(self, n: int, k: int) -> int:
        if n | k != n: return -1
        return bin(n & ~k).count('1')
Rust
impl Solution {
    pub fn min_bit_changes(n: i32, k: i32) -> i32 {
        if (n | k) != n { return -1; }
        (n & !k).count_ones() as i32
    }
}
TypeScript
function minBitChanges(n: number, k: number): number {
    if ((n | k) !== n) return -1;
    let diff = n & ~k, cnt = 0;
    while (diff > 0) { cnt += diff & 1; diff >>= 1; }
    return cnt;
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Comments