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)\).

Python3JavaC++GoTypeScript

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

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);
    }
};

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;
}

Comments