C++로 배열 전체의 XOR을 0으로 만드는 최소 연산 횟수 구하기

문제 개요

n개의 요소로 이루어진 배열이 주어졌을 때, 배열 전체의 XOR 값을 0으로 만드는 것이 목표입니다. 이를 위해 다음과 같은 작업을 수행할 수 있습니다.

먼저 배열에서 임의의 요소 하나를 선택한 뒤,

• 선택한 요소의 값을 1씩 증가시키거나 감소시킬 수 있습니다.
• 배열 전체의 XOR 합이 0이 되도록 만들기 위해 선택한 요소에 적용해야 하는 최소 증가/감소 연산 횟수를 구해야 합니다.

예제

예를 들어 arr[] = {2, 4, 7}이라면 연산은 단 1번만 필요합니다.

• 요소 2를 선택합니다.
• 값을 1 증가시켜 3으로 만듭니다.
• 배열은 {3, 4, 7}이 되고, XOR 값은 3 ^ 4 ^ 7 = 0이 됩니다.

알고리즘

1. 배열 전체의 XOR 값을 계산합니다.
2. 요소 arr[i]를 선택했다고 가정하면, 해당 요소에 필요한 비용(연산 횟수)은 abs(arr[i] − (XOR합 ^ arr[i]))입니다. 여기서 XOR합 ^ arr[i]는 arr[i]를 제외한 나머지 요소들의 XOR 값과 같습니다.
3. 모든 요소에 대해 이 절대값을 계산한 뒤, 그중 최솟값이 곧 필요한 최소 연산 횟수입니다.

C++ 구현 예제

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getMinCost(int *arr, int n) {
    int operations = INT_MAX;
    int elem;
    int xorValue = 0;
    for (int i = 0; i < n; ++i) {
        xorValue = xorValue ^ arr[i];
    }
    for (int i = 0; i < n; ++i) {
        if (operations > abs((xorValue ^ arr[i]) - arr[i])) {
            operations = abs((xorValue ^ arr[i]) - arr[i]);
            elem = arr[i];
        }
    }
    cout << "Element= " << elem << endl;
    cout << "Minimum required operations = " << abs(operations) << endl;
}
int main() {
    int arr[] = {2, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    getMinCost(arr, n);
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Element = 2
Minimum required operations = 1

복잡도 분석

이 알고리즘은 배열을 두 번 선형 순회하므로 시간 복잡도는 O(n)입니다. 또한 추가적인 자료구조 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)로, 크기가 큰 입력에서도 효율적으로 동작합니다.