# Number of Bit Changes to Make Two Integers Equal
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-bit-changes-to-make-two-integers-equal)
Canonical: https://scaleengineer.com/dsa/problems/number-of-bit-changes-to-make-two-integers-equal
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [ThoughtWorks](https://scaleengineer.com/companies/thoughtworks)
---
## 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.

**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 <= 106`

# Approaches
## String Conversion and Comparison
This approach involves converting both integers `n` and `k` into their binary string representations. After ensuring both strings have the same length by padding the shorter one with leading zeros, we can iterate through them character by character to check for the conditions of the problem.
**Time:** O(log(max(n, k))). The length of the binary representation of a number `x` is proportional to `log(x)`. String operations like conversion and padding take time proportional to this length. · **Space:** O(log(max(n, k))) to store the binary string representations of `n` and `k`.
**Pros:** Conceptually straightforward, especially for those more comfortable with string manipulation than bitwise operations.
**Cons:** Inefficient due to the overhead of string creation, concatenation (for padding), and character-by-character access.; The implementation is more verbose compared to bitwise solutions.
### Explanation
The core idea is to work with the numbers as text.
1.  First, we obtain the binary strings for `n` and `k` using `Integer.toBinaryString()`.
2.  The binary strings might have different lengths. To compare them bit by bit, we need to align them. We find the maximum length and pad the shorter string with leading '0's until it matches the maximum length.
3.  We then iterate through the aligned strings from left to right (most significant to least significant bit).
4.  For each position `i`, we compare the characters `n_str.charAt(i)` and `k_str.charAt(i)`.
    *   If `n` has a '0' where `k` has a '1', the transformation is impossible, as we cannot change a '0' to a '1'. We return -1 immediately.
    *   If `n` has a '1' where `k` has a '0', this is a required change. We increment a counter.
    *   If the bits are the same, no action is needed.
5.  If the loop completes without finding an impossible case, the final value of the counter is our answer.
```java
class Solution {
    public int minChanges(int n, int k) {
        String nStr = Integer.toBinaryString(n);
        String kStr = Integer.toBinaryString(k);

        int nLen = nStr.length();
        int kLen = kStr.length();
        int maxLen = Math.max(nLen, kLen);

        // Pad with leading zeros to make lengths equal
        while (nStr.length() < maxLen) {
            nStr = "0" + nStr;
        }
        while (kStr.length() < maxLen) {
            kStr = "0" + kStr;
        }

        int changes = 0;
        for (int i = 0; i < maxLen; i++) {
            char nBit = nStr.charAt(i);
            char kBit = kStr.charAt(i);

            if (nBit == '0' && kBit == '1') {
                return -1; // Impossible to change 0 to 1
            }
            if (nBit == '1' && kBit == '0') {
                changes++; // Required change from 1 to 0
            }
        }
        return changes;
    }
}
```
### Algorithm
*   Convert `n` and `k` to binary strings, `nStr` and `kStr`.
*   Determine the maximum length between `nStr` and `kStr`.
*   Pad the shorter string with leading zeros to match the maximum length.
*   Initialize a `changes` counter to 0.
*   Iterate through the strings from `i = 0` to `length - 1`.
*   At each position `i`, compare `nStr.charAt(i)` and `kStr.charAt(i)`.
*   If `nStr.charAt(i) == '0'` and `kStr.charAt(i) == '1'`, return -1.
*   If `nStr.charAt(i) == '1'` and `kStr.charAt(i) == '0'`, increment `changes`.
*   After the loop, return `changes`.

## Iterative Bit-by-Bit Comparison
This approach avoids the overhead of string conversion by working directly with the integer representations. We can inspect the bits of `n` and `k` one by one, from the least significant bit upwards, using bitwise operators.
**Time:** O(log(max(n, k))) or O(B) where B is the number of bits in the integer type (e.g., 32). The loop runs once for each bit position until both numbers are zero. · **Space:** O(1). We only use a few integer variables to store the count and intermediate bit values, regardless of the input size.
**Pros:** Much more efficient than the string-based approach as it avoids allocations and string operations.; Uses constant extra space.
**Cons:** Can be slightly less intuitive than string manipulation for those unfamiliar with bitwise operators.
### Explanation
Instead of converting numbers to strings, we can use bitwise operations to achieve the same goal more efficiently. The logic remains the same: compare each corresponding bit of `n` and `k`.
We can use a loop that continues as long as either `n` or `k` is not zero. In each iteration, we examine the last bit (least significant bit) of both numbers.
1.  The last bit of a number `x` can be obtained using the bitwise AND operation: `x & 1`.
2.  We compare `n & 1` and `k & 1`.
    *   If `n`'s last bit is 0 (`(n & 1) == 0`) and `k`'s last bit is 1 (`(k & 1) == 1`), the transformation is impossible. We return -1.
    *   If `n`'s last bit is 1 and `k`'s last bit is 0, we must perform a change. We increment our `changes` counter.
3.  After checking the last bits, we discard them by right-shifting both `n` and `k` by one position (`n >>= 1`, `k >>= 1`). This makes the next bits the new last bits for the next iteration.
4.  The loop terminates when both `n` and `k` become 0, meaning we have processed all their bits.
```java
class Solution {
    public int minChanges(int n, int k) {
        int changes = 0;
        // Loop until all bits of both n and k have been processed
        while (n > 0 || k > 0) {
            int nBit = n & 1; // Get the last bit of n
            int kBit = k & 1; // Get the last bit of k

            if (nBit == 0 && kBit == 1) {
                return -1; // Impossible case: cannot change 0 to 1
            }
            if (nBit == 1 && kBit == 0) {
                changes++; // Required change: 1 to 0
            }

            // Move to the next bit
            n >>= 1;
            k >>= 1;
        }
        return changes;
    }
}
```
### Algorithm
*   Initialize a `changes` counter to 0.
*   Start a loop that continues as long as `n > 0` or `k > 0`.
*   Inside the loop, get the least significant bit of `n` (`n_bit = n & 1`) and `k` (`k_bit = k & 1`).
*   If `n_bit` is 0 and `k_bit` is 1, return -1.
*   If `n_bit` is 1 and `k_bit` is 0, increment `changes`.
*   Right-shift both `n` and `k` by one bit (`n >>= 1`, `k >>= 1`) to process the next pair of bits.
*   After the loop finishes, return `changes`.

## Optimized Bitwise Logic
This is the most efficient approach, leveraging the properties of bitwise operations to solve the problem in a very concise and fast manner. It separates the problem into two parts: checking for impossibility and counting the changes, both of which can be done with single bitwise expressions.
**Time:** O(1). The bitwise AND, comparison, and `Integer.bitCount` operations are typically single, highly optimized machine instructions. · **Space:** O(1). No extra space proportional to the input size is used.
**Pros:** Extremely efficient in both time and space.; Very concise and elegant code.; Leverages hardware-optimized instructions for bit counting on many platforms.
**Cons:** Requires a good understanding of bitwise logic, which might make it less immediately obvious than other methods.
### Explanation
This solution is based on two key bitwise insights.

**1. Impossibility Check:**
The transformation from `n` to `k` is only possible if for every bit that is set to `1` in `k`, the corresponding bit is also `1` in `n`. We cannot create a `1` bit where `n` has a `0`. This property is perfectly captured by the bitwise AND operation. If `(n & k) == k`, it means that all set bits in `k` are also set in `n`. If `(n & k) != k`, it implies there is at least one bit position where `k` has a `1` and `n` has a `0`, making the transformation impossible.

**2. Counting Changes:**
If the transformation is possible, we need to count the number of bits that must be flipped from `1` to `0`. These are the bits that are `1` in `n` but `0` in `k`. Since we've already established that all of `k`'s `1`s are also `1`s in `n`, the number of bits to change is simply the total number of `1`s in `n` minus the number of `1`s in `k`. The `1`s in `k` are the ones we *don't* change. The number of set bits is also known as the population count (popcount). Most languages provide a built-in function for this, like `Integer.bitCount()` in Java.

The algorithm is therefore extremely simple:
1. Check if `(n & k) != k`. If true, return -1.
2. Otherwise, return `Integer.bitCount(n) - Integer.bitCount(k)`.

```java
class Solution {
    public int minChanges(int n, int k) {
        // Check for the impossible case: k has a '1' where n has a '0'.
        // If (n & k) is not equal to k, it means there's a bit set in k
        // that is not set in n.
        if ((n & k) != k) {
            return -1;
        }

        // If possible, the number of changes is the number of bits that are '1' in n
        // but '0' in k. This is equivalent to the difference in the total number
        // of set bits in n and k.
        return Integer.bitCount(n) - Integer.bitCount(k);
    }
}
```
### Algorithm
*   Check if `k` is a "bitwise subset" of `n` by evaluating the condition `(n & k) == k`.
*   If the condition is false, it's impossible to form `k` from `n`. Return -1.
*   If the condition is true, the transformation is possible. The number of required changes (flipping a `1` in `n` to a `0`) is the number of set bits in `n` minus the number of set bits in `k`.
*   Return the result of `Integer.bitCount(n) - Integer.bitCount(k)`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

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

```