이 문제에서는 N개의 정수 배열이 제공됩니다. 우리의 임무는 구성될 수 있는 부분 수열의 개수를 찾는 것입니다. 따라서 해당 요소를 곱하면 2의 거듭제곱이 되는 숫자가 됩니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - arr =[2, 5, 4]
출력 - 3
설명 - 하위 시퀀스 [2], [4] 및 [2, 4]는 원하는 결과를 제공합니다.
이 문제를 해결하려면 권력의 논리를 이해해야 합니다.
2의 거듭제곱이 있는 숫자만 곱하여 원하는 결과를 얻습니다. 따라서 배열 자체가 2의 거듭제곱인 하위 시퀀스만 고려해야 합니다.
따라서 배열에 2의 거듭제곱인 M개의 요소가 있는 경우 하위 배열의 개수는 2 M 이 됩니다. - 1
예시
솔루션 구현을 보여주는 프로그램
#include <iostream>
#include <math.h>
using namespace std;
bool isPowerTwo(int num) {
if (num == 0)
return false;
if (num == 1)
return true;
if (num & (num - 1))
return false;
return true;
}
int SubsequenceWithPowerTwo(int arr[], int N) {
int count = 0;
for (int i = 0; i < N; i++)
if (isPowerTwo(arr[i]))
count++;
return (int)(pow(2, count)) - 1;
}
int main() {
int arr[] = {5, 4, 8, 12, 32, 9 };
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"No. of subsequences which multiply to a number which is a power of 2 are : ";
cout<<SubsequenceWithPowerTwo(arr, N)<<endl;
return 0;
} 출력
No. of subsequences which multiply to a number which is a power of 2 are : 7