Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

Leetcode Daily Challenge Day 6: 2429. Minimize XOR

First Thoughts & Intuition

Chào anh em, các ae có thể xem Đề bàiSolution của mình trên LeetCode nhé:

2429. Minimize XOR

Medium
Solved Topics Companies

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.

Example 1:

Input: num1 = 3, num2 = 5
Output: 3
Explanation:
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.

Example 2:

Input: num1 = 1, num2 = 12
Output: 3
Explanation:
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

Problem Analysis

Bài toán yêu cầu chúng ta tìm một số nguyên x thỏa mãn:

  1. x có cùng số lượng bit 1 với num2
  2. Giá trị x XOR num1 là nhỏ nhất có thể

Detailed Approach

Mình sẽ chia sẻ cách tiếp cận theo từng bước:

1. Ý Tưởng Chính

C++


1. Ví dụ trực quan: 

```
num1 = 3 (11)

num2 = 4 (100)

```

- Ta cần tạo số x có cùng số lượng bit 1 với num2 (tức là 1 bit)

- Khi XOR với num1, ta muốn kết quả càng nhỏ càng tốt

- Điều này có nghĩa là x nên giống num1 càng nhiều càng tốt

2. Tại sao lại chọn x = 2?

- num1 = 3 (11)

- Các lựa chọn cho x với 1 bit 1: (1, 2, 4, 8,...)

- Nếu chọn x = 1 (01): 3 XOR 1 = 2

- Nếu chọn x = 2 (10): 3 XOR 2 = 1

- Nếu chọn x = 4 (100): 3 XOR 4 = 7

3. Quy luật quan trọng:

- Khi XOR, bit giống nhau cho kết quả 0

- Bit khác nhau cho kết quả 1

- Do đó, ta muốn x có càng nhiều bit giống với num1 càng tốt

2. Chiến Lược Tối Ưu

  1. Đếm số bit 1 trong num2:
  • Dùng phép AND với 1 và dịch phải
  • Đây sẽ là số bit 1 cần có trong x
  1. Tham lam trong việc đặt bit:
  • Ưu tiên dùng các bit 1 từ num1
  • Nếu thiếu, thêm bit 1 vào vị trí thấp nhất
  1. Tối ưu XOR:
  • Bit giống num1 cho XOR = 0
  • Chọn vị trí bit hợp lý để minimize XOR

Code Implementation

C++
class Solution {

public:
    // Hàm đếm số bit 1 trong một số
    int countSetBits(int n) {
        int count = 0;
        while (n) {
            count += n & 1;  // Kiểm tra bit cuối
            n >>= 1;        // Dịch phải
        }
        return count;
    }

    // Hàm tạo số x với k bit 1, align với num1
    int createMinNumberWithSetBits(int k, int num1) {
        int ans = 0;
        // Dùng bit từ num1 trước
        for (int i = 31; i >= 0 && k > 0; --i) {
            if ((num1 >> i) & 1) {
                ans |= (1 << i);
                --k;
            }
            //Nếu sài hết bit 1 trả về ans
            if(k == 0) return ans;
        }
        // Nếu cần thêm bit 1, đặt vào vị trí thấp nhất
        for (int i = 0; i <= 31 && k > 0; ++i) {
            if (!((ans >> i) & 1)) {
                ans |= (1 << i);
                --k;
            }
      //Nếu sài hết bit 1 trả về ans
            if(k == 0) return ans;
        }
        return ans;
    }

    // Hàm chính để minimize XOR
    int minimizeXor(int num1, int num2) {
        int setBitsNum2 = countSetBits(num2);
        return createMinNumberWithSetBits(setBitsNum2, num1);
    }
};

Test Case

C++
int main() {
    Solution sol;
    
    // Test Case 1
    int num1 = 3, num2 = 4;
    cout << "Test Case 1:" << endl;
    cout << "num1 = " << num1 << " (" << bitset<4>(num1) << ")" << endl;
    cout << "num2 = " << num2 << " (" << bitset<4>(num2) << ")" << endl;
    int result = sol.minimizeXor(num1, num2);
    cout << "Result = " << result << " (" << bitset<4>(result) << ")" << endl;
    cout << "XOR = " << (result ^ num1) << endl << endl;
    
    // Test Case 2
    num1 = 7; num2 = 1;
    cout << "Test Case 2:" << endl;
    cout << "num1 = " << num1 << " (" << bitset<4>(num1) << ")" << endl;
    cout << "num2 = " << num2 << " (" << bitset<4>(num2) << ")" << endl;
    result = sol.minimizeXor(num1, num2);
    cout << "Result = " << result << " (" << bitset<4>(result) << ")" << endl;
    cout << "XOR = " << (result ^ num1) << endl << endl;
    
    // Test Case 3: Edge case với số lớn
    num1 = 255; num2 = 1;
    cout << "Test Case 3:" << endl;
    cout << "num1 = " << num1 << " (" << bitset<8>(num1) << ")" << endl;
    cout << "num2 = " << num2 << " (" << bitset<8>(num2) << ")" << endl;
    result = sol.minimizeXor(num1, num2);
    cout << "Result = " << result << " (" << bitset<8>(result) << ")" << endl;
    cout << "XOR = " << (result ^ num1) << endl;
    
    return 0;
}

Complexity Analysis

  • Time complexity: $O(1)$ - xử lý tối đa 32 bit
  • Space complexity: $O(1)$ - chỉ dùng vài biến

Tips & Tricks

  1. Với bài bit manipulation, vẽ binary ra giấy rất có ích
  2. Tư duy tham lam trong việc chọn bit rất quan trọng
  3. Đừng quên check edge cases với số 0 và các bit đặc biệt

Code Editor

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Máy lọc dầu chân không inox. Heavy equipment transport pierce wa logi transports fast & reliable heavy equipment transport & transport services.