[LeetCode] 2429. Minimize XOR (Python)

 

난이도: Medium

 

문제 설명

---

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 integer3 has the same number of set bits as num2, and the value3 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 integer3 has the same number of set bits as num2, and the value3 XOR 1 = 2 is minimal.

 

제한 사항

---

• 1 <= num1, num2 <= 10^9

 

Solution(솔루션)

---

def change_bin_num1(bin_num1, need, f, t):
    for i in range(len(bin_num1)-1, -1, -1):
        if need == 0:
            break
        elif bin_num1[i] == f:
            bin_num1[i] = t
            need -= 1

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        bin_num1 = list(bin(num1)[2:])
        bin_num2 = list(bin(num2)[2:])

        if len(bin_num2) > len(bin_num1):
            bin_num1 = ['0'] * (len(bin_num2) - len(bin_num1)) + bin_num1
        else:
            bin_num2 = ['0'] * (len(bin_num1) - len(bin_num2)) + bin_num2

        num1_one = bin_num1.count('1')
        num2_one = bin_num2.count('1')

        if num1_one == num2_one:
            return num1
        elif num1_one < num2_one:
            need = num2_one - num1_one
            change_bin_num1(bin_num1, need, '0', '1')
        else:
            need = num1_one - num2_one
            change_bin_num1(bin_num1, need, '1', '0')

        return int(''.join(bin_num1), 2)

 

"x XOR num1"이 최소가 되어야 하기 때문에 x는 최대한 num1과 같은 수여야 한다.

 

x has the same number of set bits as num2  <=  만약 이 조건이 없었으면 x는 무조건 num1과 같은 수 일 것이다.

 

하지만 위 조건이 있기 때문에, 먼저 num1의 1의 갯수와 num2의 1의 갯수를 count를 통해 얻었다.

 

만약 두 수가 같으면 그냥 num1을 반환하면 된다. num1 XOR num1은 0이기 때문에 제일 작기 때문이다. 또한 same number of set bits as num2 조건도 만족한다.

 

같지 않다고 한다면 다음과 같이 greedy하게 풀 수 있다.

만약, num1의 1의 갯수보다 num2의 1의 갯수가 많다고 한다면, num1에 (num2의 1의 갯수 - num1의 1의 갯수) 만큼 1을 추가해야한다.

하지만 최대한 작아야하기 때문에 뒤에서부터 0을 1로 바꾸면된다.

 

예를 들어 num1이 011001 이고 num2가 110110 이라고 한다면, x는 num1에서 1이 한개가 더 추가되어야한다.

따라서 x는 011011이 될 수 있다. <= 이것이 num2와 set bit도 만족하고, x XOR num1도 최대한 최소가 된다.

 

num1의 1의 갯수가 num2의 1의 갯수보다 많다고 한다면, 반대로 하면 된다. 뒤에서부터 1을 0으로 바꿔주면된다.

예를 들어 num1이 011110 이고, num2가 110000이라고 한다면 x는 num1에서 1이 2개가 빠져야한다.

따라서 x는 011000이 될 수 있다. <= 이것이 num2와 set bit도 만족하고, x XOR num1도 최대한 최소가 된다.

 

마지막으로 이를 int로 바꾸어 return하면 된다.

---

문제: 2429. Minimize XOR

 

깃허브: github

algorithmPractice/LeetCode/2509-minimize-xor at main · laewonJeong/algorithmPractice