[leetcode] Minimum Number of Operations to Make Array XOR Equal to K

문제

• 문제 링크
• 정수 배열 nums와 양수 k가 주어진다. nums에 있는 모든 수의 xor 결과가 k와 같아지게 만들어야 한다. nums에 있는 수에 대해서 몇 번이고 비트를 플립할 수 있을 때 k와 같아지게 만드는 최소 플립 횟수를 구해야 한다.
• 제약 조건
  • nums 배열 길이: 1 <= nums.length <= 10^5
  • nums 값 범위: 0 <= nums[i] <= 10^6
  • k 값 범위: 0 <= k <= 10^6
• 예시
  

풀이

풀기 전

• 처음엔 nums에 있는 수를 이진수로 변환한 다음 한 자리씩 xor 하고 k와 비교하려고 했다. 그런데 그럴 필요 없이, nums에 있는 모든 수를 xor 한 다음 k와 비교하면 되는 문제였다. 이진수로 변환할 필요도 없었다.
• xor은 값이 같으면 0을 반환하고 값이 다르면 1을 반환하는 게이트이다.

코드

class Solution {
    public int minOperations(int[] nums, int k) {
        int num = nums[0];
        for (int i=1; i<nums.length; i++)
            num ^= nums[i];  // nums에 있는 값들을 모두 xor 한다.

        int ret = 0;
        // 한 자리씩 값이 다른지 비교한다.
        while (num > 0 || k > 0) {
        	// 값이 다르면 비트플립 한 번이 필요하다.
            if (num % 2 != k % 2)
                ret++;
                
            num /= 2;
            k /= 2;
        }
        return ret;
    }
}

푼 후

• nums에 있는 값들을 xor 연산하는 시간이 있으므로 시간 복잡도는 O(nums.length)이다. 값이 다른지 비교하는 반복문도 있지만, 주어진 값의 최댓값이 10^6이므로 이진수로 변환해도 20자리밖에 안 된다.
• 상수 공간만 추가되므로 공간 복잡도는 O(1)이다.