양의 정수로 이루어진 배열이 주어졌을 때, 각 숫자에 최대 한 번 1을 더하는 연산을 적용하여 2의 거듭제곱으로 만들 수 있는 숫자의 개수를 구하는 것이 목표입니다.
이 문제는 log2() 함수를 활용해 해결할 수 있습니다. 어떤 수 x가 2의 거듭제곱이라면 log2(x)는 정수가 됩니다. 따라서 각 원소에 대해 log2 값의 floor(내림)와 ceil(올림)이 같은지 확인하고, 그렇지 않다면 1을 더한 값에 대해 다시 검사하여 조건을 만족하면 카운트를 증가시킵니다.
예제로 이해하기
입력 − arr[] = {1, 3, 2, 5, 6}
출력 − 2의 거듭제곱이 될 수 있는 숫자의 개수: 3
설명 − 1+1=2 → 2¹, 3+1=4 → 2², 2 = 2¹. 반면 5+1=6, 6+1=7은 2의 거듭제곱이 아니므로 제외됩니다.
입력 − arr[] = {2, 4, 8, 16}
출력 − 2의 거듭제곱이 될 수 있는 숫자의 개수: 4
설명 − 네 숫자 모두 이미 2의 거듭제곱이므로 추가 연산 없이 모두 개수에 포함됩니다.
알고리즘 접근 방식
- 임의의 양의 정수로 초기화된 배열 arr[]를 준비합니다.
- powofTwo(int arr[], int n) 함수는 배열과 배열의 길이를 입력받아, 2의 거듭제곱이거나 1을 더해 2의 거듭제곱으로 만들 수 있는 숫자의 개수를 반환합니다.
- 카운트 변수 count를 0으로 초기화합니다.
- i = 0부터 i < n까지 배열을 순회합니다.
- 각 원소마다 floor(log2(arr[i])) == ceil(log2(arr[i])) 또는 floor(log2(arr[i]+1)) == ceil(log2(arr[i]+1)) 조건을 검사하고, 참이면 count를 증가시킵니다.
- 순회가 끝나면 count를 최종 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int powofTwo(int arr[], int n){
int count = 0;
for(int i = 0; i < n; i++){
if( floor(log2(arr[i])) == ceil(log2(arr[i])) )
{ count++; }
else{
++arr[i];
if( floor(log2(arr[i])) == ceil(log2(arr[i])) )
{ count++; }
}
}
return count;
}
int main(){
int Arr[] = { 5, 6, 9, 3, 1 };
int len = sizeof(Arr)/sizeof(Arr[0]);
cout<<endl<<"Count of numbers with power of 2 possible: "<<powofTwo(Arr,len);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of numbers with power of 2 possible: 2
핵심 정리
위 예제에서 3+1=4(2²)와 1(2⁰) 두 개만 조건을 만족하므로 결과는 2가 됩니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 참고로 log2 기반 판별은 매우 큰 수에서 부동소수점 오차가 발생할 수 있으므로, (x & (x-1)) == 0 같은 비트 연산을 함께 고려하면 더 안정적인 구현이 가능합니다.