Jobs

Interviews

Discussions

Minimize XOR

Medium

Amazon

1 view

Topics:

Bit ManipulationGreedy Algorithms

Given two positive integers num1 and num2, find the positive integer x such that:

x has the same number of set bits as num2, and
The value x XOR num1 is minimal.

Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

For example:

If num1 = 3 and num2 = 5, the output should be 3. The binary representations of num1 and num2 are 0011 and 0101, respectively. The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.

As another example, if num1 = 1 and num2 = 12, the output should be 3. The binary representations of num1 and num2 are 0001 and 1100, respectively. The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.

Constraints:

1 <= num1, num2 <= 10^9

Minimize XOR

Medium

Amazon

1 view

Topics:

Bit ManipulationGreedy Algorithms

Given two positive integers num1 and num2, find the positive integer x such that:

x has the same number of set bits as num2, and
The value x XOR num1 is minimal.

Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

For example:

Constraints:

1 <= num1, num2 <= 10^9

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds on the values of num1 and num2?
Is it guaranteed that num2 will always have a number of set bits that allows for a valid x to be created, or should I handle cases where no solution is possible?
If there are multiple values of x that minimize the value of x XOR num1 while still having the correct number of set bits, what should I return?
Are num1 and num2 guaranteed to be positive integers, or could they be zero?
By 'minimize x', do you mean minimize the numerical value of x, or minimize the value of x XOR num1 (subject to the set bits constraint)?

Brute Force Solution

Approach

The brute force method for this problem involves trying every conceivable number. We will go through each possible number, checking if it meets the criteria, and choose the best number that fits the conditions of the problem.

Here's how the algorithm would work step-by-step:

Start with the smallest possible number.
Check if the number has the correct number of ones.
If it does, calculate the XOR of this number and the given number.
If it doesn't have the correct number of ones, move on to the next number.
Keep track of the number that results in the minimum XOR so far.
Continue with the next number and repeat the above steps until we have tried all possible numbers within the allowed range.
Finally, select the number with the minimum XOR value that satisfied all of the requirements.

Code Implementation

def minimize_xor_brute_force(number, num_of_set_bits):    minimum_xor = float('inf')
    result = -1
    maximum_possible_number = 2 ** 31 - 1

    for current_number in range(maximum_possible_number + 1):
        # We need to check the number of set bits
        if bin(current_number).count('1') == num_of_set_bits:

            current_xor = number ^ current_number

            # This is to check for the minimum value
            if current_xor < minimum_xor:

                minimum_xor = current_xor
                result = current_number

    return result

Big(O) Analysis

Time Complexity

O(2^n) – The brute force algorithm iterates through all possible numbers within a range. Since we are considering all possible numbers to minimize the XOR, and assuming an n-bit representation for the numbers involved, this means we iterate from 0 to 2^n - 1. For each number, we count the number of set bits (ones), which can take O(n) time in the worst case. The overall process thus involves iterating through all 2^n possible numbers.

Space Complexity

O(1) – The provided brute force method iterates through numbers, calculating the XOR and comparing with a minimum value found so far. This approach only requires a few integer variables to store the current number, the count of ones, the XOR result, and the minimum XOR value. The space used by these variables remains constant regardless of the range of possible numbers being checked. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find a number that, when combined with a given number using the XOR operation, results in the smallest possible value while having the same number of set bits as another given number. The strategy is to iteratively build the result by considering the bits of the first number from most significant to least significant and setting bits in the result accordingly.

Here's how the algorithm would work step-by-step:

First, count the number of set bits (1s) in the second given number. This tells us how many set bits our final answer must have.
Start examining the first given number from its leftmost bit (the most significant bit) and move towards the right.
If a bit in the first number is a 0, and we still need to set more bits in our answer (i.e., we haven't reached the required number of set bits), then set the corresponding bit in our answer to 1. This will minimize the XOR result because XORing 0 with 1 gives 1, but XORing 1 with 1 gives 0.
If a bit in the first number is a 1, and we have enough set bits in our answer already (or setting it would exceed the required number of set bits), then set the corresponding bit in our answer to 0. This minimizes the XOR result because XORing 1 with 0 gives 1, but XORing 0 with 0 gives 0.
If a bit in the first number is a 1, and we still need to set more bits in our answer, then set the corresponding bit in our answer to 1. This will result in a zero in that position for the XOR result, which is good.
After going through all the bits of the first number, if we still haven't reached the target number of set bits, then start setting the rightmost (least significant) zero bits in the answer to one, until we reach the desired count. Conversely, if there are too many set bits in the constructed number, clear (set to zero) the rightmost set bits until the counts match.
The result will be the number that has the same number of set bits as the second given number and when XORed with the first given number yields the minimum possible value.

Code Implementation

def minimize_xor(number1, number2):
    set_bits_in_number2 = bin(number2).count('1')
    result = 0
    bit_length = number1.bit_length()

    for i in range(bit_length - 1, -1, -1):
        bit_value = (number1 >> i) & 1

        # Prioritize setting bits where number1 has 0 to minimize XOR
        if bit_value == 0:
            if set_bits_in_number2 > 0:
                result |= (1 << i)
                set_bits_in_number2 -= 1

        # If number1 has 1, try to set 0 in result if possible.
        else:
            if set_bits_in_number2 > 0:
                result |= (1 << i)
                set_bits_in_number2 -= 1

    # Adjust result if necessary to match the number of set bits
    set_bits_in_result = bin(result).count('1')

    #Correct for too few bits
    if set_bits_in_result < bin(number2).count('1'):
        for i in range(bit_length):
            if set_bits_in_number2 == 0:
                break
            if (result >> i) & 1 == 0:
                result |= (1 << i)
                set_bits_in_number2 -= 1

    #Correct for too many bits
    if bin(result).count('1') > bin(number2).count('1'):
        for i in range(bit_length):
            if bin(result).count('1') == bin(number2).count('1'):
                break

            #Clear the bits from right to left
            if (result >> i) & 1 == 1:
                result &= ~(1 << i)

    return result

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iterates through the bits of the first number. The number of bits in a number is logarithmic with respect to its value. Thus, the primary loop which constructs the result runs in O(log n) time, where n is the value of the input number. The final adjustments to set or clear bits also occur in at most O(log n) time. Therefore, the overall time complexity is O(log n).

Space Complexity

O(1) – The algorithm primarily uses a fixed number of integer variables such as the count of set bits, the result, and potentially loop counters. No auxiliary data structures like arrays, lists, or hash maps are created that scale with the input numbers. The space used is therefore constant and independent of the input numbers, 'a' and 'b', making the space complexity O(1).

Edge Cases

Case	How to Handle
num1 or num2 is zero	The solution should correctly handle zero inputs by counting zero set bits and adjusting x accordingly.
num1 and num2 are equal and have the same number of set bits	The smallest x is 0, which can be achieved if num1 and num2 have the same bits set.
num2 has more set bits than the maximum number of bits in num1	If num2 has more set bits than the number of bits in num1, then it would be impossible to create x as it would require more set bits than num1, so ensure code won't fail.
num2 has zero set bits	In this case, x XOR num1 must have no set bits, meaning x must be equal to num1.
num1 and num2 are both maximum integer values (2^31 - 1)	The solution should still correctly calculate the XOR based on maximizing set bits of x by trying from LSB.
num2 has all bits set to 1 (maximum value)	This maximizes the number of set bits for the target number of set bits in x XOR num1.
Integer overflow while calculating intermediate values	Use appropriate data types or bit manipulation techniques to prevent overflow during calculations, for example consider unsigned integer types.
Maximum possible input values for num1 and num2 are large causing inefficiency.	The solution should use bitwise operations which are O(1) and scalable with large numbers, instead of converting numbers to strings or lists for bit counting.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds on the values of num1 and num2?
Is it guaranteed that num2 will always have a number of set bits that allows for a valid x to be created, or should I handle cases where no solution is possible?
If there are multiple values of x that minimize the value of x XOR num1 while still having the correct number of set bits, what should I return?
Are num1 and num2 guaranteed to be positive integers, or could they be zero?
By 'minimize x', do you mean minimize the numerical value of x, or minimize the value of x XOR num1 (subject to the set bits constraint)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the smallest possible number.
Check if the number has the correct number of ones.
If it does, calculate the XOR of this number and the given number.
If it doesn't have the correct number of ones, move on to the next number.
Keep track of the number that results in the minimum XOR so far.
Continue with the next number and repeat the above steps until we have tried all possible numbers within the allowed range.
Finally, select the number with the minimum XOR value that satisfied all of the requirements.

Code Implementation

def minimize_xor_brute_force(number, num_of_set_bits):    minimum_xor = float('inf')
    result = -1
    maximum_possible_number = 2 ** 31 - 1

    for current_number in range(maximum_possible_number + 1):
        # We need to check the number of set bits
        if bin(current_number).count('1') == num_of_set_bits:

            current_xor = number ^ current_number

            # This is to check for the minimum value
            if current_xor < minimum_xor:

                minimum_xor = current_xor
                result = current_number

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count the number of set bits (1s) in the second given number. This tells us how many set bits our final answer must have.
Start examining the first given number from its leftmost bit (the most significant bit) and move towards the right.
If a bit in the first number is a 0, and we still need to set more bits in our answer (i.e., we haven't reached the required number of set bits), then set the corresponding bit in our answer to 1. This will minimize the XOR result because XORing 0 with 1 gives 1, but XORing 1 with 1 gives 0.
If a bit in the first number is a 1, and we have enough set bits in our answer already (or setting it would exceed the required number of set bits), then set the corresponding bit in our answer to 0. This minimizes the XOR result because XORing 1 with 0 gives 1, but XORing 0 with 0 gives 0.
If a bit in the first number is a 1, and we still need to set more bits in our answer, then set the corresponding bit in our answer to 1. This will result in a zero in that position for the XOR result, which is good.
After going through all the bits of the first number, if we still haven't reached the target number of set bits, then start setting the rightmost (least significant) zero bits in the answer to one, until we reach the desired count. Conversely, if there are too many set bits in the constructed number, clear (set to zero) the rightmost set bits until the counts match.
The result will be the number that has the same number of set bits as the second given number and when XORed with the first given number yields the minimum possible value.

Code Implementation

def minimize_xor(number1, number2):
    set_bits_in_number2 = bin(number2).count('1')
    result = 0
    bit_length = number1.bit_length()

    for i in range(bit_length - 1, -1, -1):
        bit_value = (number1 >> i) & 1

        # Prioritize setting bits where number1 has 0 to minimize XOR
        if bit_value == 0:
            if set_bits_in_number2 > 0:
                result |= (1 << i)
                set_bits_in_number2 -= 1

        # If number1 has 1, try to set 0 in result if possible.
        else:
            if set_bits_in_number2 > 0:
                result |= (1 << i)
                set_bits_in_number2 -= 1

    # Adjust result if necessary to match the number of set bits
    set_bits_in_result = bin(result).count('1')

    #Correct for too few bits
    if set_bits_in_result < bin(number2).count('1'):
        for i in range(bit_length):
            if set_bits_in_number2 == 0:
                break
            if (result >> i) & 1 == 0:
                result |= (1 << i)
                set_bits_in_number2 -= 1

    #Correct for too many bits
    if bin(result).count('1') > bin(number2).count('1'):
        for i in range(bit_length):
            if bin(result).count('1') == bin(number2).count('1'):
                break

            #Clear the bits from right to left
            if (result >> i) & 1 == 1:
                result &= ~(1 << i)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
num1 or num2 is zero	The solution should correctly handle zero inputs by counting zero set bits and adjusting x accordingly.
num1 and num2 are equal and have the same number of set bits	The smallest x is 0, which can be achieved if num1 and num2 have the same bits set.
num2 has more set bits than the maximum number of bits in num1	If num2 has more set bits than the number of bits in num1, then it would be impossible to create x as it would require more set bits than num1, so ensure code won't fail.
num2 has zero set bits	In this case, x XOR num1 must have no set bits, meaning x must be equal to num1.
num1 and num2 are both maximum integer values (2^31 - 1)	The solution should still correctly calculate the XOR based on maximizing set bits of x by trying from LSB.
num2 has all bits set to 1 (maximum value)	This maximizes the number of set bits for the target number of set bits in x XOR num1.
Integer overflow while calculating intermediate values	Use appropriate data types or bit manipulation techniques to prevent overflow during calculations, for example consider unsigned integer types.
Maximum possible input values for num1 and num2 are large causing inefficiency.	The solution should use bitwise operations which are O(1) and scalable with large numbers, instead of converting numbers to strings or lists for bit counting.