Đếm tất cả các dãy con có tích <=K - Phương pháp đệ quy trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số chuỗi con có tích <=k.

Đối với điều này, chúng tôi sẽ được cung cấp một mảng và một giá trị K. Nhiệm vụ của chúng tôi là tìm số chuỗi con có tích của chúng là K.

Ví dụ

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

Đầu ra

9