Skip to main content

Minimize XOR | LeetCode 2429 | Bit Manipulation |

If you're preparing for coding interviews or competitive programming, "Minimize XOR" is a fascinating problem to test your understanding of bit manipulation.

Problem

You are given two positive integers, num1 and num2. Your task is to find a positive integer x such that:

  1. x has the same number of set bits (1s in its binary representation) as num2.

  2. The value of x XOR num1 is minimized.

The result must be uniquely determined, and the test cases are guaranteed to meet this condition.

What is XOR?

Before we jump into the solution, let’s quickly revisit what XOR (Exclusive OR) is. XOR is a bitwise operation:

  • If two bits are the same (both 0 or both 1), the result is 0.

  • If two bits are different (one is 0, the other is 1), the result is 1.

To achieve this, we need to be as "similar" as possible to , especially in the higher significant bits.

Understand the Problem with Examples

Let’s go through a couple of examples to understand the requirements better:

Example 1:

  • Input: num1 = 3, num2 = 5

  • Number of set bits in : 2

We need to construct an integer that:

  • Has exactly 2 set bits.

Example 2:

  • Input: num1 = 1, num2 = 12

  • Number of set bits : 2

Again, we need with exactly 2 set bits, minimizing .

Approach to Solve the Problem

The problem boils down to constructing such that:

  1. It has the same number of set bits.

  2. The difference between and (in terms of bit values) is minimal.

To achieve this, we follow these steps:

Step 1: Count Set Bits in num2

Count the number of set bits (1s) in nums2. Let’s call this count . This tells us how many bits in need to be set to num1.

Step 2: Reuse Set Bits from num1

To minimize , we prioritize reusing the set bits (1s) from MSB. Starting from the most significant bit of num1, we check if a bit is set (1). If it is, we include it in and reduce by 1.

Step 3: Fill Remaining Bits

If after processing all bits of num1, we set the remaining bits in x, starting from the least significant bit (to keep as small as possible).

Step 4: Return the Result

Finally, return as the result.

Algorithm

  1. Count the number of set bits in num2.

  2. Initialize x = 0 .

  3. Iterate through the bits of from the most significant bit to the least significant bit:

    • If the current bit of is set (1), set the corresponding bit in and decrement .

    • Stop when reaches 0.

  4. If , iterate through all bits starting from the least significant bit:

    • Set the bit in x, if it is not already set.

    • Decrement after each change.

  5. Return x.

Complexity Analysis

  • Time Complexity: O(1)

    • We iterate through a fixed number of bits (32 for integers).

  • Space Complexity: O(1)

    • We use a constant amount of extra space.

Code

#include <iostream>
using namespace std;

int minimizeXor(int num1, int num2)
{
    // Step 1: Count the number of set bits in num2
    int setBitsNum2 = __builtin_popcount(num2); // Built-in function to count set bits
    int x = 0;

    // Step 2: Reuse the set bits from num1
    for (int i = 31; i >= 0; --i)
    { // Iterate through the bits from most significant to least
        if (setBitsNum2 == 0)
            break; // Stop if we've used all required set bits
        if (num1 & (1 << i))
        {                  // Check if the i-th bit of num1 is set
            x |= (1 << i); // Set the i-th bit of x
            setBitsNum2--; // Decrease the remaining set bits count
        }
    }

    // Step 3: Add remaining set bits in x from the least significant bit
    for (int i = 0; i < 32; ++i)
    {
        if (setBitsNum2 == 0)
            break; // Stop if we've matched the required number of set bits
        if (!(x & (1 << i)))
        {                  // If the i-th bit of x is not set
            x |= (1 << i); // Set the i-th bit of x
            setBitsNum2--; // Decrease the remaining set bits count
        }
    }

    return x; // Return the minimized x
}

int main()
{
    // Example 1
    int num1 = 3, num2 = 5;
    cout << "Result for num1 = 3, num2 = 5: " << minimizeXor(num1, num2) << endl;

    // Example 2
    num1 = 1, num2 = 12;
    cout << "Result for num1 = 1, num2 = 12: " << minimizeXor(num1, num2) << endl;

    return 0;
}



Tags:

Bit Manipulation
Leetcode
Minimise XOR
Leetcode Todays Question

Popular posts from this blog

Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that: One of the characters has an even frequency . The other character has an odd frequency . The difference is calculated as:  odd_frequency - even_frequency We need to return the maximum possible difference between the odd and even frequencies. Example Walkthrough Let's take a couple of examples to better understand the problem: Example 1: Input:  s = "aaaaabbc" Frequencies: 'a' → 5 (odd) 'b' → 2 (even) 'c' → 1 (odd) Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is: maxOdd - maxEven = 5 - 2 = 3 Example 2: Input:  s = "abcabcab" Frequencies: 'a' → 3 (odd) 'b' → 2 (even) 'c' → 2 (even) The maximum odd frequency is 3 (for 'a') and the maximum even fr...
Read more

Top 10 Beginner-Friendly LeetCode Questions and Their Solutions

If you're new to solving coding problems on LeetCode, it can feel overwhelming. Where do you start? Which problems are suitable for beginners? Don’t worry! In this blog post, I’ll guide you through   10 beginner-friendly LeetCode questions   that are perfect for getting started on your coding journey. These problems will help you build confidence, improve your problem-solving skills, and lay a solid foundation in data structures and algorithms. Why Start with Beginner-Friendly Problems? Before diving into advanced topics like dynamic programming or graph theory, it’s essential to: Build a strong foundation in basic programming concepts. Understand how to approach a coding problem methodically. Gain familiarity with LeetCode’s platform and its problem structure. The following problems are simple yet impactful, designed to introduce you to common techniques like loops, arrays, strings, and basic math operations. 10 Beginner-Friendly LeetCode Problems 1.  Two Sum (Easy) Prob...
Read more

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....
Read more