C++ 비트 XOR 연산으로 결과가 홀수(ODD)가 되는 쌍 개수 구하기

문제 개요

정수 배열이 주어졌을 때, 배열의 원소들로 만들 수 있는 모든 쌍(pair) 중에서 XOR(배타적 논리합) 연산의 결과가 홀수(ODD)가 되는 쌍의 총 개수를 구하는 것이 이 글의 목표입니다.

XOR은 두 비트가 서로 다를 때만 1을 반환하는 연산입니다. 먼저 XOR 연산의 진리표부터 살펴보겠습니다.

XOR 연산의 진리표

예제 입력 및 출력

입력 − int arr[] = {2, 8, 1, 5, 11}

출력 − XOR 결과가 홀수인 쌍의 개수: 6

설명

배열 {2, 8, 1, 5, 11}에서 만들 수 있는 모든 쌍과 각각의 XOR 연산 결과는 다음과 같습니다.

위 표에서 XOR 결과가 홀수인 쌍은 (2, 1), (2, 5), (2, 11), (8, 1), (8, 5), (8, 11)로 총 6개입니다.

핵심 아이디어

모든 쌍을 일일이 검사하기 전에 XOR의 성질을 활용하면 문제를 훨씬 단순화할 수 있습니다. XOR 결과가 홀수가 되려면 두 수 중 하나는 짝수, 다른 하나는 홀수여야 합니다.

• 짝수 XOR 짝수 = 짝수
• 홀수 XOR 홀수 = 짝수
• 짝수 XOR 홀수 = 홀수

따라서 배열에서 짝수의 개수를 count, 전체 원소 개수를 size라고 하면 홀수의 개수는 (size - count)이며, XOR 결과가 홀수가 되는 쌍의 개수는 다음 공식으로 바로 계산할 수 있습니다.

쌍의 개수 = count × (size - count)

알고리즘 접근 방식

• 쌍을 만들 정수 배열을 입력받습니다.
• 배열의 크기를 계산한 뒤, 데이터를 함수에 전달해 처리합니다.
• 짝수 원소의 개수를 저장할 임시 변수 count를 선언합니다.
• i를 0부터 배열 크기까지 반복하면서 arr[i] % 2 == 0이면 count를 증가시킵니다.
• 홀수가 되는 쌍의 개수를 count * (size - count)로 계산합니다.
• 결과를 반환하고 출력합니다.

이 방법은 이중 반복문 없이 한 번의 순회만으로 답을 구할 수 있으므로 시간 복잡도는 O(n)입니다.

예제 코드

#include <iostream>
using namespace std;
//XOR 결과가 홀수인 쌍의 개수를 세는 함수
int XOR_Odd(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 == 0){
            count++;
        }
    }
    int odd = count * (size-count);
    return odd;
}
int main(){
    int arr[] = { 6, 1, 3, 4, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs with Bitwise XOR as ODD number are: "<<XOR_Odd(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of pairs with Bitwise XOR as ODD number are: 9

배열 {6, 1, 3, 4, 8, 9}에는 짝수가 6, 4, 8로 3개, 홀수가 1, 3, 9로 3개 있습니다. 따라서 3 × 3 = 9개의 쌍에서 XOR 연산 결과가 홀수가 됩니다.

마무리

XOR 연산의 패리티 특성만 이해하면, 브루트 포스 방식(O(n²)) 대신 짝수와 홀수의 개수만 세어 곱하는 O(n) 알고리즘으로 문제를 해결할 수 있습니다. 배열의 크기가 커질수록 이 최적화의 효과는 더욱 커집니다.