# 3226. Number of Bit Changes to Make Two Integers Equal

## Description

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.

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 = (0100)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 <= 106

## Solutions

### Solution 1: Bit Manipulation

If the bitwise AND result of $n$ and $k$ is not equal to $k$, it indicates that there exists at least one bit where $k$ is $1$ and the corresponding bit in $n$ is $0$. In this case, it is impossible to modify a bit in $n$ to make $n$ equal to $k$, and we return $-1$. Otherwise, we count the number of $1$s in the binary representation of $n \oplus k$.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$.

• class Solution {
public int minChanges(int n, int k) {
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
}
}

• class Solution {
public:
int minChanges(int n, int k) {
return (n & k) != k ? -1 : __builtin_popcount(n ^ k);
}
};

• class Solution:
def minChanges(self, n: int, k: int) -> int:
return -1 if n & k != k else (n ^ k).bit_count()


• func minChanges(n int, k int) int {
if n&k != k {
return -1
}
return bits.OnesCount(uint(n ^ k))
}

• function minChanges(n: number, k: number): number {
return (n & k) !== k ? -1 : bitCount(n ^ k);
}

function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}