[LeetCode] 2997. Minimum Number of Operations to Make Array XOR Equal to K

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-xor-equal-to-k/description/

leetcode - Minimum Number of Operations to Make Array XOR Equal to K

문제 유형 : 비트마스킹, 비트 조작

문제 난이도 : Medium

 

문제

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와 정수 k가 주어집니다.

당신은 몇 번이고 nums의 요소의 이진 표현에서의 비트를 하나 바꿀 수 있습니다.

0 -> 1, 1 -> 0 둘다 가능합니다. 한번에 하나의 연산을 한 것으로 칩니다.

 

nums의 모든 요소를 bitwise XOR 하였을 때 k가 나오도록 하는 연산의 최소 횟수를 구하시오.

맨 앞에 있는 0도 1로 바꿀 수 있습니다. 즉, 101(0101)을 1101로 바꿀 수 있습니다.

 

풀이

nums의 모든 xor한 값이 k가 되려면,

우선 nums를 모두 xor한 값에서 어떤 숫자와 xor해야 k가 되는지 알아야 한다.

몇 번째 비트들을 각각 뒤집어야 하는지 알아야 하기 때문이다.

어떤 숫자를 골라서 비트를 반전시키는지는 중요하지 않다.

앞에 있는 0도 1로 바꿀 수 있으니, 그냥 한 숫자를 집어서 뒤집는다는 것이 중요하다.

 

nums = [2,1,3,4], k = 1을 생각해보자.

2,1,3,4를 모두 xor하면 100 = 4이다.

1의 이진 표현은 001이다.

즉, 100 XOR ㅁ = 001에서 ㅁ을 찾아야 하는데,

ㅁ = 100 XOR 001 = 101임을 알 수 있다.

4의자리와 1의자리 비트를 한 번씩 뒤집어야 한다는 뜻이다.

즉, ㅁ을 구한 다음, 그 숫자의 이진 표현에서의 1의 개수를 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int ans = 0;
        int x = nums[0];

        for(int i = 1; i < nums.size(); i++) {
            x ^= nums[i];
        }

        x ^= k;

        while(x > 0) {
            x = x & x-1;
            ans++;
        }
        return ans;
    }
};