সাবসিকোয়েন্স যার গুণফল ২-এর ঘাত (C++)

এই সমস্যায় N সংখ্যক ইন্টিজারের একটি অ্যারে দেওয়া আছে। এমন সাবসিকোয়েন্সগুলো কতটিতে গুণফল ২-এর ঘাত হয় তা গণনা করতে হবে।

উদাহরণ

ইনপুট: arr = [2, 5, 4]

আউটপুট: 3

ব্যাখ্যা: সাবসিকোয়েন্স [2], [4] এবং [2, 4] — এগুলোর গুণফল ২-এর ঘাত।

লজিক

শুধু ২-এর ঘাতবाले উপাদানগুলোই মিলে ২-এর ঘাত দিতে পারে। তাই অ্যারেতে যেসব উপাদান ২-এর ঘাত, তাদের সংখ্যা M হলে সাবসিকোয়েন্সের সংখ্যা = 2ᴹ - ১।

C++ প্রোগ্রাম

#include <iostream>
#include <cmath>
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 << "গুণফল ২-এর ঘাত হয় এমন সাবসিকোয়েন্সের সংখ্যা: ";
    cout << SubsequenceWithPowerTwo(arr, N) << endl;
    return 0;
}

আউটপুট

গুণফল ২-এর ঘাত হয় এমন সাবসিকোয়েন্সের সংখ্যা: 7