Lũy thừa của 2 và dãy con trong C++

Trong bài toán này, ta được cho một mảng N số nguyên. Nhiệm vụ là đếm số lượng dãy con (subsequence) sao cho nếu nhân các phần tử của dãy con đó thì kết quả là một số là lũy thừa của 2.

Hãy xem ví dụ:

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

Đầu ra – 3

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

Để giải bài toán, cần hiểu logic của lũy thừa.

Chỉ những số là lũy thừa của 2 mới nhân với nhau cho kết quả là lũy thừa của 2. Do đó, ta chỉ xét các dãy con tạo thành từ các phần tử bản thân đã là lũy thừa của 2.

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

Ví dụ minh họa

Chương trình triển khai giải pháp:

#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<<"Số dãy con nhân được lũy thừa của 2: ";    cout<<SubsequenceWithPowerTwo(arr, N)<<endl;    return 0; }

Kết quả

Số dãy con nhân được lũy thừa của 2 là: 7