[2024] day 121. Leetcode 2997. Minimum Number of Operations to Make Array XOR Equal to K

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 29일 (월)
Leetcode daily problem

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/?envType=daily-question&envId=2024-04-29

Problem

0부터 시작하는 정수 배열 nums와 양의 정수 k가 있을 때, 배열에 다음 작업을 여러 번 적용한다.

• 배열의 요소를 선택하고 이진수로 표현하고 비트를 뒤집는다. 비트를 뒤집는다는 것은 0을 1로 또는 그 반대로 변경하는 것을 의미한다.

최종 배열의 모든 요소에 대한 비트별 XOR을 k와 동일하게 만드는 데 필요한 최소 연산 수를 반환한다.

요소의 이진 표현에서 0 비트를 뒤집을 수 있는데, 예를 들어 숫자 (101)2의 경우 네 번째 비트를 뒤집으면 (1101)2이다.

Solution

Bit Manipulation

해당 문제는 비트 조작을 통해서 해결한다.
비트 XOR 연산은 비트가 다르면 1을 반환하고 같으면 0을 반환한다.
3개의 비트의 조합도 마찬가지인데,
세 비트의 XOR을 계산하려면 처음 두 비트를 XOR한 다음 해당 연산의 결과를 세 번째 비트와 XOR하면 된다.

자세히 살펴보면 1비트의 수가 홀수이면 XOR의 결과가 1이고 그렇지 않으면 0의 값이 나오는 것을 볼 수 있는데,
이는 XOR이

N 비트가 0이면 짝수

N 비트는 1로 설정됩니다. 한 비트를 뒤집어 1 비트 수를 홀수로 만들면 XOR의 결과는 1이 됩니다. 마찬가지로

N 비트는 1이고 그 다음 홀수입니다.

N 비트는 1로 설정됩니다. 다시 한 비트를 뒤집어 1비트의 수를 짝수로 만들면 XOR 결과가 0으로 변경됩니다. 따라서 XOR 결과를 변경하려면 항상 단일 비트를 뒤집어야 합니다.

N 비트.

우리는 이 문제를 해결하기 위해 위의 관찰을 사용할 것입니다. 모든 XOR을 가정해보자.

nums 배열의 N개 정수는 finalXor입니다. 우리는 이 finalXor가 K이길 원합니다. 우리는 finalXor와 K의 이진 표현을 비교할 것입니다. 비트 불일치 수는 필요한 최소 작업 수입니다. 왜냐하면 finalXor와 K 사이의 각 비트 차이는 해당 비트를 뒤집기 위해 한 번의 작업이 필요하기 때문이다.
즉 이를 구현하기 위해 finalXOR를 찾은 다음 K와 finalXOR의 이진 표현을 비교하여 일치하지 않는 비트를 찾는 것이다.

XOR 연산을 사용하면 구현을 단순화할 수 있는데, 먼저 finalXor와 K 사이에 일치하지 않는 비트 수를 찾는다.
finalXOR과 K의 XOR을 찾으면 결과의 이진 표현에는 finalXor와 K의 비트가 일치하지 않는 각 비트 위치에 대해 1이 포함됩니다. 일치하지 않습니다. finalXor와 K를 XOR할 수 있으며, 결과에서 1로 설정된 각 비트 위치는 피연산자의 비트가 일치하지 않는 위치입니다. 그런 다음 결과에서 설정된 비트 수(값 1), 즉 최소 작업 수를 계산할 수 있습니다. 설정된 비트 수를 계산하기 위해 표준 라이브러리 함수를 사용하겠습니다.

연산
finalXor 변수를 0으로 초기화합니다.
nums 배열의 요소를 반복하고 finalXor 변수를 사용하여 각 요소의 XOR을 찾습니다.
변수 finalXor에 설정된 비트 수를 반환합니다.

Code

Complexicity

시간 복잡도

공간 복잡도