Number of Bit Changes to Make Two Integers Equal

• 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.

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.

1class Solution {2    public int minChanges(int n, int k) {3        String nStr = Integer.toBinaryString(n);4        String kStr = Integer.toBinaryString(k);5 6        int nLen = nStr.length();7        int kLen = kStr.length();8        int maxLen = Math.max(nLen, kLen);9 10        // Pad with leading zeros to make lengths equal11        while (nStr.length() < maxLen) {12            nStr = "0" + nStr;13        }14        while (kStr.length() < maxLen) {15            kStr = "0" + kStr;16        }17 18        int changes = 0;19        for (int i = 0; i < maxLen; i++) {20            char nBit = nStr.charAt(i);21            char kBit = kStr.charAt(i);22 23            if (nBit == '0' && kBit == '1') {24                return -1; // Impossible to change 0 to 125            }26            if (nBit == '1' && kBit == '0') {27                changes++; // Required change from 1 to 028            }29        }30        return changes;31    }32}

• 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.

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.

1class Solution {2    public int minChanges(int n, int k) {3        int changes = 0;4        // Loop until all bits of both n and k have been processed5        while (n > 0 || k > 0) {6            int nBit = n & 1; // Get the last bit of n7            int kBit = k & 1; // Get the last bit of k8 9            if (nBit == 0 && kBit == 1) {10                return -1; // Impossible case: cannot change 0 to 111            }12            if (nBit == 1 && kBit == 0) {13                changes++; // Required change: 1 to 014            }15 16            // Move to the next bit17            n >>= 1;18            k >>= 1;19        }20        return changes;21    }22}

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

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 1s are also 1s in n, the number of bits to change is simply the total number of 1s in n minus the number of 1s in k. The 1s 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).

1class Solution {2    public int minChanges(int n, int k) {3        // Check for the impossible case: k has a '1' where n has a '0'.4        // If (n & k) is not equal to k, it means there's a bit set in k5        // that is not set in n.6        if ((n & k) != k) {7            return -1;8        }9 10        // If possible, the number of changes is the number of bits that are '1' in n11        // but '0' in k. This is equivalent to the difference in the total number12        // of set bits in n and k.13        return Integer.bitCount(n) - Integer.bitCount(k);14    }15}