Quyền hạn của hai và dãy con trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng N số nguyên. Nhiệm vụ của chúng tôi là tìm số lượng các dãy con có thể được tạo thành sao cho nếu các phần tử của chúng được nhân lên, chúng sẽ dẫn đến một số là lũy thừa của hai.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - arr =[2, 5, 4]

Đầu ra - 3

Giải thích - dãy con [2], [4] và [2, 4] cho kết quả mong muốn.

Để giải quyết vấn đề này, chúng ta cần hiểu logic của quyền lực.

Chỉ những số có lũy thừa của 2 sẽ nhân lên để cho kết quả mong muốn. Vì vậy, chúng ta chỉ phải xem xét những dãy con từ mảng mà bản thân nó là một số lũy thừa của 2.

Vì vậy, nếu trong mảng có M phần tử là lũy thừa của 2, thì số mảng con sẽ là 2 ^M - 1

Ví dụ

Chương trình thể hiện việc triển khai giải pháp của chúng tôi

#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;
}

Đầu ra

No. of subsequences which multiply to a number which is a power of 2 are : 7