[LeetCode] 2997. Minimum Number of Operations to Make Array XOR Equal to K (Daily Question)

문제

---

You are given a 0-indexed integer array nums and a positive integer k.

You can apply the following operation on the array any number of times:

    - Choose any element of the array and flip a bit in its binary representation. Flipping a bit means changing a 0 to 1 or vice versa.

Return the minimum number of operations required to make the bitwise XOR of all elements of the final array equal to k.

Note that you can flip leading zero bits in the binary representation of elements. For example, for the number (101)2 you can flip the fourth bit and obtain (1101)2.

 

정수들을 담은 리스트 nums가 주어졌을 때, nums내의 정수중 하나를 골라 비트 하나를 바꿀 수 있다. 7=0111 -> 15=1111

모든 정수를 xor처리해서 k와 같게 만들기 위해 바꿔야 할 비트의 개수의 최소값을 구하는 문제이다.

 

Example 1:
Input: nums = [2,1,3,4], k = 1
Output: 2
Explanation: We can do the following operations: - Choose element 2 which is 3 == (011)2, we flip the first bit and we obtain (010)2 == 2. nums becomes [2,1,2,4]. - Choose element 0 which is 2 == (010)2, we flip the third bit and we obtain (110)2 = 6. nums becomes [6,1,2,4]. The XOR of elements of the final array is (6 XOR 1 XOR 2 XOR 4) == 1 == k. It can be shown that we cannot make the XOR equal to k in less than 2 operations.

Example 2:
Input: nums = [2,0,2,0], k = 0
Output: 0
Explanation: The XOR of elements of the array is (2 XOR 0 XOR 2 XOR 0) == 0 == k. So no operation is needed.

 

풀이

---

아이디어

- xor연산은 값이 하나만 바껴도 결과 값이 바뀐다. (0^0^0^0^0=0  1^0^0^0^0=1)

- nums내의 모든 정수 xor ^ k 를 하면 바꿔야 할 비트만 1이 된다.

 

 

코드

from functools import reduce

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        xor = reduce(lambda acc, cur: acc^cur, nums)
        dif = abs(xor^k)

        return str(bin(dif)).count('1')

 

---

 

후기

---

비트연산문제는 많이 안풀어 봐서 별 생각이 없었는데, 이번 문제는 꽤나 재밌는 문제였다고 생각한다.

xor의 특징을 알고 있다면 쉽게 풀 수 있는 문제였다.