3226. Number of Bit Changes to Make Two Integers Equal

EasyBit Manipulation

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

Intuition

In this problem, the key observation is to check if k can be formed from n by only changing some of the '1' bits in n to '0'.

Condition for Impossibility: If there is a bit that is 1 in k but 0 in n, no amount of flipping '1' bits in n to '0' will create that '1' bit in the resulting number. This condition is checked using the bitwise AND operation. If n & k is not equal to k, it means there are '1' bits in k which are '0' in n, making the transformation impossible. Therefore, we return -1 if n & k != k.
Counting Changes: If it's possible to transform n into k, the next step is to determine how many changes are needed. By performing a bitwise XOR operation n ^ k, we identify the differing bits between n and k. The number of bits that are '1' in the result of n ^ k represents the bits that need to be flipped from '1' to '0' in n to match k. Thus, the result of (n ^ k).bit_count() gives us the number of changes needed.

This approach efficiently assesses possibility and calculates the required operations using simple bitwise operations.

Solution Approach

The solution utilizes bitwise operations to determine the number of changes needed to transform n into k by changing certain '1' bits in n to '0'.

Check Possibility Using Bitwise AND:
- Perform a bitwise AND operation between n and k, denoted as n & k.
- If the result is not equal to k, it indicates that k has some '1' bits that are '0' in n, making the transformation impossible. Thus, return -1.
```
if n & k != k:
    return -1
```
Calculate Required Changes with Bitwise XOR:
- Use the bitwise XOR operation n ^ k to find the differences between n and k.
- The XOR operation highlights differences by producing a binary number with '1's in positions where n and k have different bits.
- Count the number of '1's in the result using the method .bit_count(), which gives the number of changes required.
```
return (n ^ k).bit_count()
```

This solution is efficient and leverages the properties of bitwise operations to quickly determine both the possibility of transformation and the number of operations required.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with n = 14 and k = 8.

Step 1: Check Possibility Using Bitwise AND

First, we use the bitwise AND operation between n and k:
n & k = 14 & 8 = 8
We compare the result with k. Since 8 is equal to 8, it's possible to transform n into k.

Step 2: Calculate Required Changes with Bitwise XOR

Next, we perform a bitwise XOR operation to find the differing bits:
n ^ k = 14 ^ 8 = 6
The binary representation of 6 is 110, indicating the differing bits are at two positions.
By counting the number of '1's in 6 (110 in binary), we determine two changes are needed. The method .bit_count() confirms this result.

Thus, the number of changes required to transform n = 14 into k = 8 by turning certain '1' bits to '0' is 2.

Solution Implementation

1class Solution:
2    def minChanges(self, n: int, k: int) -> int:
3        # Check if 'k' is a subset of 'n' (i.e., all bits in 'k' are also set in 'n').
4        if n & k != k:
5            # Return -1 if 'k' is not a subset of 'n'.
6            return -1
7      
8        # Calculate the XOR of 'n' and 'k'.
9        xor_value = n ^ k
10
11        # Count the number of 1-bits in the XOR result, which represents the number of bit changes required.
12        return xor_value.bit_count()
13

1class Solution {
2    /**
3     * Calculates the minimum number of bit changes needed to convert number 'n' to number 'k'
4     * @param n the original integer
5     * @param k the target integer
6     * @return the minimum number of changes, or -1 if 'n' cannot be converted to 'k'
7     */
8    public int minChanges(int n, int k) {
9        // Check if all bits in k exist in n
10        // If not, return -1 since it's impossible to convert n to k
11        if ((n & k) != k) {
12            return -1;
13        } 
14        // Calculate the number of differing bits between n and k
15        // This represents the minimum number of bit changes needed
16        return Integer.bitCount(n ^ k);
17    }
18}
19

1class Solution {
2public:
3    // Function to compute the minimum number of bit changes needed
4    // to convert the integer n into integer k.
5    int minChanges(int n, int k) {
6        // Check if all bits set in 'k' are also set in 'n'; if not, return -1.
7        // This checks if 'n' AND 'k' equals 'k'. If not, it's impossible
8        // to match 'k' because some set bits in 'k' are not set in 'n'.
9        if ((n & k) != k) {
10            return -1;
11        }
12      
13        // Calculate the number of differing bits between 'n' and 'k'.
14        // The XOR operation (n ^ k) gives a number with bits set
15        // where 'n' and 'k' differ; the __builtin_popcount function
16        // then counts the number of such differing bits.
17        return __builtin_popcount(n ^ k);
18    }
19};
20

1// Function to calculate the minimum number of changes required
2// to make all bits of 'n' match 'k'. Returns -1 if it's not possible.
3function minChanges(n: number, k: number): number {
4    // Check if all bits in 'k' are set in 'n'
5    if ((n & k) !== k) {
6        return -1; // Return -1 if 'k' can't be matched with 'n'
7    }
8    // Calculate the number of differing bits between 'n' and 'k'
9    return bitCount(n ^ k);
10}
11
12// Function to count the number of set bits (1s) in an integer
13function bitCount(i: number): number {
14    // Subtracting pairs of bits and combining results
15    i = i - ((i >>> 1) & 0x55555555);
16    // Adding groups of four bits
17    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
18    // Summing the bits in each byte
19    i = (i + (i >>> 4)) & 0x0f0f0f0f;
20    // Combine all bits within each 8-bit segment
21    i = i + (i >>> 8);
22    // Combine all bits within each 16-bit segment resulting in counts in lower 6 bits
23    i = i + (i >>> 16);
24    // Return the count of set bits in the lowest 6 bits
25    return i & 0x3f;
26}
27

Time and Space Complexity

The given function minChanges performs a few constant-time operations:

n & k != k checks whether all bits of k are set in n. This takes O(1) time since it's a bitwise operation.
n ^ k computes the bitwise XOR of n and k, also an O(1) operation.
(n ^ k).bit_count() counts the number of 1 bits in the result of the XOR operation. In Python, this operation effectively measures the Hamming weight of the number, which takes O(\log n) time, as it needs to examine each bit of the integer representation, where n is the number of bits.

Thus, the overall time complexity of the function is O(\log n), primarily due to the bit count operation.

Regarding space complexity, the function only uses a constant amount of space for calculations, qualifying it as O(1).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: