Given an integer K and a non-negative array arr[], the task is to find the number of sub-sequences having the product ? K.
This problem already has a dynamic programming solution. This solution aims to provide an optimized recursive strategy to the problem.
Examples:
Input: arr[] = { 1, 2, 3, 4 }, K = 10
Output: 11
The sub-sequences are {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}Input: arr[] = { 4, 8, 7, 2 }, K = 50
Output: 9
Approach: Convert the product problem to a sum problem by performing the conversions arr[i] = log(arr[i]) and K = log(K). Generate all subsets and store the sum of elements that have been taken in the sub-sequence. If at any point, the sum becomes larger than K, then we know that if we add another element to the sub-sequence, its sum will also be larger than K. Therefore, we discard all such sub-sequences that have sum larger than K without making a recursive call for them. Also, if we currently have sum less than K then we check if there are any chances to further discard any sub-sequences. If any further sub-sequences can’t be discarded, then no recursive calls are made.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach.#include <bits/stdc++.h>#define ll long longusing namespace std;// This variable counts discarded subsequencesll discard_count = 0;// Function to return a^nll 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 function that counts discarded // subsequencesvoid solve(int i, int n, float sum, float k, float* a, float* prefix){ // If at any stage, sum > k // discard further subsequences if (sum > k) { discard_count += power(2, n - i); // Recursive call terminated // No further calls return; } if (i == n) return; // rem = Sum of array[i+1...n-1] float rem = prefix[n - 1] - prefix[i]; // If there are chances of discarding // further subsequences then make a // recursive call, otherwise not // Including a[i] if (sum + a[i] + rem > k) solve(i + 1, n, sum + a[i], k, a, prefix); // Excluding a[i] if (sum + rem > k) solve(i + 1, n, sum, k, a, prefix);}// Function to return count of non-empty // subsequences whose product doesn't// exceed kint countSubsequences(const int* arr, int n, ll K){ float sum = 0.0; // Converting k to log(k) float k = log2(K); // Prefix sum array and array to // store log values. float prefix[n], a[n]; // a[] is the array obtained // after converting numbers to // logarithms for (int i = 0; i < n; i++) { a[i] = log2(arr[i]); sum += a[i]; } // Computing prefix sums prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Calculate non-empty subsequences // hence 1 is subtracted ll total = power(2, n) - 1; // If total sum is <= k, then // answer = 2^n - 1 if (sum <= k) { return total; } solve(0, n, 0.0, k, a, prefix); return total - discard_count;}// Driver codeint main(){ int arr[] = { 4, 8, 7, 2 }; int n = sizeof(arr) / sizeof(arr[0]); ll k = 50; cout << countSubsequences(arr, n, k); return 0;} |
Java
// Java implementation of the above approach.class GFG{// This variable counts discarded subsequencesstatic long discard_count = 0;// Function to return a^nstatic long power(long a, long n){ if (n == 0) return 1; long p = power(a, n / 2); p = p * p; if (n % 2 == 1) p = p * a; return p;}// Recursive function that counts discarded // subsequencesstatic void solve(int i, int n, float sum, float k, float []a, float []prefix){ // If at any stage, sum > k // discard further subsequences if (sum > k) { discard_count += power(2, n - i); // Recursive calong terminated // No further calongs return; } if (i == n) return; // rem = Sum of array[i+1...n-1] float rem = prefix[n - 1] - prefix[i]; // If there are chances of discarding // further subsequences then make a // recursive calong, otherwise not // Including a[i] if (sum + a[i] + rem > k) solve(i + 1, n, sum + a[i], k, a, prefix); // Excluding a[i] if (sum + rem > k) solve(i + 1, n, sum, k, a, prefix);}// Function to return count of non-empty // subsequences whose product doesn't// exceed kstatic int countSubsequences(int []arr, int n, long K){ float sum = 0.0f; // Converting k to log(k) float k = (float) Math.log(K); // Prefix sum array and array to // store log values. float []prefix = new float[n]; float []a = new float[n]; // a[] is the array obtained // after converting numbers to // logarithms for (int i = 0; i < n; i++) { a[i] = (float) Math.log(arr[i]); sum += a[i]; } // Computing prefix sums prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Calculate non-empty subsequences // hence 1 is subtracted long total = power(2, n) - 1; // If total sum is <= k, then // answer = 2^n - 1 if (sum <= k) { return (int) total; } solve(0, n, 0.0f, k, a, prefix); return (int) (total - discard_count);}// Driver codepublic static void main(String[] args){ int arr[] = { 4, 8, 7, 2 }; int n = arr.length; long k = 50; System.out.print(countSubsequences(arr, n, k));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the # above approach. # From math lib import log2from math import log2# This variable counts discarded# subsequences discard_count = 0# Function to return a^n def power(a, n) : if (n == 0) : return 1 p = power(a, n // 2) p = p * p if (n & 1) : p = p * a return p # Recursive function that counts # discarded subsequences def solve(i, n, sum, k, a, prefix) : global discard_count # If at any stage, sum > k # discard further subsequences if (sum > k) : discard_count += power(2, n - i) # Recursive call terminated # No further calls return; if (i == n) : return # rem = Sum of array[i+1...n-1] rem = prefix[n - 1] - prefix[i] # If there are chances of discarding # further subsequences then make a # recursive call, otherwise not # Including a[i] if (sum + a[i] + rem > k) : solve(i + 1, n, sum + a[i], k, a, prefix) # Excluding a[i] if (sum + rem > k) : solve(i + 1, n, sum, k, a, prefix)# Function to return count of non-empty # subsequences whose product doesn't # exceed k def countSubsequences(arr, n, K) : sum = 0.0 # Converting k to log(k) k = log2(K) # Prefix sum array and array to # store log values. prefix = [0] * n a = [0] * n # a[] is the array obtained after # converting numbers to logarithms for i in range(n) : a[i] = log2(arr[i]) sum += a[i] # Computing prefix sums prefix[0] = a[0] for i in range(1, n) : prefix[i] = prefix[i - 1] + a[i] # Calculate non-empty subsequences # hence 1 is subtracted total = power(2, n) - 1 # If total sum is <= k, then # answer = 2^n - 1 if (sum <= k) : return total solve(0, n, 0.0, k, a, prefix) return total - discard_count # Driver code if __name__ == "__main__" : arr = [ 4, 8, 7, 2 ] n = len(arr) k = 50; print(countSubsequences(arr, n, k))# This code is contributed by Ryuga |
C#
// C# implementation of the above approach.using System;class GFG{// This variable counts discarded subsequencesstatic long discard_count = 0;// Function to return a^nstatic long power(long a, long n){ if (n == 0) return 1; long p = power(a, n / 2); p = p * p; if (n % 2 == 1) p = p * a; return p;}// Recursive function that counts discarded // subsequencesstatic void solve(int i, int n, float sum, float k, float []a, float []prefix){ // If at any stage, sum > k // discard further subsequences if (sum > k) { discard_count += power(2, n - i); // Recursive calong terminated // No further calongs return; } if (i == n) return; // rem = Sum of array[i+1...n-1] float rem = prefix[n - 1] - prefix[i]; // If there are chances of discarding // further subsequences then make a // recursive calong, otherwise not // Including a[i] if (sum + a[i] + rem > k) solve(i + 1, n, sum + a[i], k, a, prefix); // Excluding a[i] if (sum + rem > k) solve(i + 1, n, sum, k, a, prefix);}// Function to return count of non-empty // subsequences whose product doesn't// exceed kstatic int countSubsequences(int []arr, int n, long K){ float sum = 0.0f; // Converting k to log(k) float k = (float) Math.Log(K); // Prefix sum array and array to // store log values. float []prefix = new float[n]; float []a = new float[n]; // []a is the array obtained // after converting numbers to // logarithms for (int i = 0; i < n; i++) { a[i] = (float) Math.Log(arr[i]); sum += a[i]; } // Computing prefix sums prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Calculate non-empty subsequences // hence 1 is subtracted long total = power(2, n) - 1; // If total sum is <= k, then // answer = 2^n - 1 if (sum <= k) { return (int) total; } solve(0, n, 0.0f, k, a, prefix); return (int) (total - discard_count);}// Driver codepublic static void Main(String[] args){ int []arr = { 4, 8, 7, 2 }; int n = arr.Length; long k = 50; Console.Write(countSubsequences(arr, n, k));}}// This code is contributed by Rajput-Ji |
PHP
<?php // PHP implementation of the above approach.// This variable counts discarded subsequences$discard_count = 0;// Function to return a^nfunction power($a, $n){ if ($n == 0) return 1; $p = power($a, $n / 2); $p = $p * $p; if ($n & 1) $p = $p * $a; return $p;}// Recursive function that counts discarded // subsequencesfunction solve($i, $n, $sum, $k, &$a, &$prefix){ global $discard_count; // If at any stage, sum > k // discard further subsequences if ($sum > $k) { $discard_count += power(2, $n - $i); // Recursive call terminated // No further calls return; } if ($i == $n) return; // rem = Sum of array[i+1...n-1] $rem = $prefix[$n - 1] - $prefix[$i]; // If there are chances of discarding // further subsequences then make a // recursive call, otherwise not // Including a[i] if ($sum + $a[$i] + $rem > $k) solve($i + 1, $n, $sum + $a[$i], $k, $a, $prefix); // Excluding a[i] if ($sum + $rem > $k) solve($i + 1, $n, $sum, $k, $a, $prefix);}// Function to return count of non-empty // subsequences whose product doesn't// exceed kfunction countSubsequences(&$arr, $n, $K){ global $discard_count; $sum = 0.0; // Converting k to log(k) $k = log($K, 2); // Prefix sum array and array to // store log values. $prefix = array_fill(0, $n, NULL); $a = array_fill(0, $n, NULL); // a[] is the array obtained after // converting numbers to logarithms for ($i = 0; $i < $n; $i++) { $a[$i] = log($arr[$i], 2); $sum += $a[$i]; } // Computing prefix sums $prefix[0] = $a[0]; for ($i = 1; $i < $n; $i++) { $prefix[$i] = $prefix[$i - 1] + $a[$i]; } // Calculate non-empty subsequences // hence 1 is subtracted $total = power(2, $n) - 1; // If total sum is <= k, then // answer = 2^n - 1 if ($sum <= $k) { return $total; } solve(0, $n, 0.0, $k, $a, $prefix); return $total - $discard_count;}// Driver code$arr = array(4, 8, 7, 2 );$n = sizeof($arr);$k = 50;echo countSubsequences($arr, $n, $k);// This code is contributed by ita_c?> |
Javascript
<script>// Javascript implementation of the above approach. // This variable counts discarded subsequenceslet discard_count = 0;// Function to return a^nfunction power(a,n){ if (n == 0) return 1; let p = power(a, Math.floor(n / 2)); p = p * p; if (n % 2 == 1) p = p * a; return p;}// Recursive function that counts discarded // subsequencesfunction solve(i,n,sum,k,a,prefix){ // If at any stage, sum > k // discard further subsequences if (sum > k) { discard_count += power(2, n - i); // Recursive calong terminated // No further calongs return; } if (i == n) return; // rem = Sum of array[i+1...n-1] let rem = prefix[n - 1] - prefix[i]; // If there are chances of discarding // further subsequences then make a // recursive calong, otherwise not // Including a[i] if (sum + a[i] + rem > k) solve(i + 1, n, sum + a[i], k, a, prefix); // Excluding a[i] if (sum + rem > k) solve(i + 1, n, sum, k, a, prefix);}// Function to return count of non-empty // subsequences whose product doesn't// exceed kfunction countSubsequences(arr,n,K){ let sum = 0.0; // Converting k to log(k) let k = Math.log(K); // Prefix sum array and array to // store log values. let prefix = new Array(n); let a = new Array(n); // a[] is the array obtained // after converting numbers to // logarithms for (let i = 0; i < n; i++) { a[i] = Math.log(arr[i]); sum += a[i]; } // Computing prefix sums prefix[0] = a[0]; for (let i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Calculate non-empty subsequences // hence 1 is subtracted let total = power(2, n) - 1; // If total sum is <= k, then // answer = 2^n - 1 if (sum <= k) { return total; } solve(0, n, 0.0, k, a, prefix); return (total - discard_count);}// Driver codelet arr=[4, 8, 7, 2];let n = arr.length;let k = 50;document.write(countSubsequences(arr, n, k));// This code is contributed by avanitrachhadiya2155</script> |
Output:
9
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
