এই টিউটোরিয়ালে আমরা প্রোডাক্ট <= K वाले সাবসিকোয়েন্সের সংখ্যা বের করার প্রোগ্রাম নিয়ে আলোচনা করব।
এই জন্য আমাদের একটি অ্যারে এবং একটি K ভ্যালু দেওয়া থাকবে। আমাদের কাজ হলো যেসব সাবসিকোয়েন্সের প্রোডাক্ট K এর সমান বা কম, সেগুলোর সংখ্যা বের করা।
উদাহরণ
#include <bits/stdc++.h> #define ll long long using namespace std; //keeping count of discarded sub sequences ll discard_count = 0; ll power(ll a, ll n){ if (n == 0) return 1; ll p = power(a, n / 2); p = p * p; if (n & 1) p = p * a; return p; } //recursive approach to count //discarded sub sequences void solve(int i, int n, float sum, float k, float* a, float* prefix){ if (sum > k) { discard_count += power(2, n - i); return; } if (i == n) return; float rem = prefix[n - 1] - prefix[i]; if (sum + a[i] + rem > k) solve(i + 1, n, sum + a[i], k, a, prefix); if (sum + rem > k) solve(i + 1, n, sum, k, a, prefix); } int countSubsequences(const int* arr, int n, ll K){ float sum = 0.0; float k = log2(K); float prefix[n], a[n]; for (int i = 0; i < n; i++) { a[i] = log2(arr[i]); sum += a[i]; } prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } ll total = power(2, n) - 1; if (sum <= k) { return total; } solve(0, n, 0.0, k, a, prefix); return total - discard_count; } int main() { int arr[] = { 4, 8, 7, 2 }; int n = sizeof(arr) / sizeof(arr[0]); ll k = 50; cout << countSubsequences(arr, n, k); return 0; }আউটপুট
9
