C ++中2和子序列的幂

在这个问题中，我们得到了N个整数的数组。我们的任务是找到可以形成的子序列数，以使得如果将它们的元素相乘，它们将得出一个为2的幂的数。

让我们举个例子来了解这个问题，

输入-arr = [2，5，4]

输出-3

说明-子序列[2]，[4]和[2、4]给出了所需的结果。

为了解决这个问题，我们需要了解权力的逻辑。

只有那些具有2的幂的数字才会相乘以提供期望的结果。因此，我们只需要考虑数组本身就是2的幂的子序列。

因此，如果数组中有M个元素的2的幂，那么子数组的数量将为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