C++로 배열에서 합이 2의 거듭제곱이 되는 쌍의 개수 구하기

배열이 주어졌을 때, 두 원소의 합이 2의 거듭제곱(1, 2, 4, 8, ...)이 되는 쌍(pair)의 개수를 구하는 문제입니다. 먼저 간단한 예시를 통해 문제를 이해해 보겠습니다.

예시

입력

arr = [1, 2, 3]

출력

1

합이 2의 거듭제곱이 되는 쌍은 (1, 3) 단 하나뿐입니다. 1 + 3 = 4이고, 4는 2²이므로 조건을 만족합니다.

알고리즘

이 문제는 브루트 포스(Brute Force) 방식으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.

• 배열을 임의의 숫자들로 초기화합니다.
• 카운트 변수를 0으로 초기화합니다.
• 두 개의 중첩 반복문을 사용해 배열의 모든 가능한 쌍을 탐색합니다.
  • 각 쌍의 합을 계산합니다.
  • 비트 AND 연산(&)을 활용해 해당 합이 2의 거듭제곱인지 확인합니다.
  • 조건을 만족하면 카운트를 1 증가시킵니다.
• 최종 카운트를 반환합니다.

2의 거듭제곱 판별 원리

(sum & (sum - 1)) == 0이라는 조건은 2의 거듭제곱을 판별하는 잘 알려진 비트 연산 기법입니다. 2의 거듭제곱 수는 이진법으로 표현했을 때 최상위 비트 하나만 1이고 나머지는 모두 0입니다(예: 8 = 1000₂). 여기서 1을 빼면 그 비트 아래의 모든 비트가 1로 바뀌게 됩니다(예: 7 = 0111₂). 따라서 두 값을 AND 연산하면 항상 0이 됩니다. 이 성질을 이용하면 별도의 루프나 로그 계산 없이 O(1) 시간에 판별할 수 있습니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int get2PowersCount(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = arr[i] + arr[j];
            if ((sum & (sum - 1)) == 0) {
                count++;
            }
        }
    }
    return count;
}
int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = 10;
    cout << get2PowersCount(arr, n) << endl;
    return 0;
}

실행 결과

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

6

예제 배열 {1, 2, ..., 10}에서 합이 2의 거듭제곱이 되는 쌍은 총 6개입니다. 시간 복잡도는 모든 쌍을 확인해야 하므로 O(n²)이며, 공간 복잡도는 O(1)입니다.