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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7


Input: n = 21, k = 21

Output: 0

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

Example 3

1
2
3
4
5
6
7


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

1
2
3
4
5
6
7
8
9

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;
    }
};
1
2
3
4
5
6

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
}
1
2
3
4
5
6
7
8

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;
    }
}
1
2
3
4
5
6
7
8

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
    }
}
1
2
3
4

class Solution:
    def minBitChanges(self, n: int, k: int) -> int:
        if n | k != n: return -1
        return bin(n & ~k).count('1')
1
2
3
4
5
6

impl Solution {
    pub fn min_bit_changes(n: i32, k: i32) -> i32 {
        if (n | k) != n { return -1; }
        (n & !k).count_ones() as i32
    }
}
1
2
3
4
5
6

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)