2の累乗とC++のサブシーケンス

この問題では、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