Number of subsets with product less than k | CPP to find the count subset having product less than k ; declare four vector for dividing array into two halves and storing product value of possible subsets for them ; ignore element greater than k and divide array into 2 halves ; ignore element if greater than k ; generate all subsets for 1 st half ( vect1 ) ; push only in case subset product is less than equal to k ; generate all subsets for 2 nd half ( vect2 ) ; push only in case subset product is less than equal to k ; sort subset2 ; for null subset decrement the value of count ; return count ; driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSubset ( long long int arr [ ] , int n , long long int k ) { vector < long long int > vect1 , vect2 , subset1 , subset2 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > k ) continue ; if ( i <= n / 2 ) vect1 . push_back ( arr [ i ] ) ; else vect2 . push_back ( arr [ i ] ) ; } for ( int i = 0 ; i < ( 1 << vect1 . size ( ) ) ; i ++ ) { long long value = 1 ; for ( int j = 0 ; j < vect1 . size ( ) ; j ++ ) { if ( i & ( 1 << j ) ) value *= vect1 [ j ] ; } if ( value <= k ) subset1 . push_back ( value ) ; } for ( int i = 0 ; i < ( 1 << vect2 . size ( ) ) ; i ++ ) { long long value = 1 ; for ( int j = 0 ; j < vect2 . size ( ) ; j ++ ) { if ( i & ( 1 << j ) ) value *= vect2 [ j ] ; } if ( value <= k ) subset2 . push_back ( value ) ; } sort ( subset2 . begin ( ) , subset2 . end ( ) ) ; long long count = 0 ; for ( int i = 0 ; i < subset1 . size ( ) ; i ++ ) count += upper_bound ( subset2 . begin ( ) , subset2 . end ( ) , ( k / subset1 [ i ] ) ) - subset2 . begin ( ) ; count -- ; return count ; } int main ( ) { long long int arr [ ] = { 4 , 2 , 3 , 6 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; long long int k = 25 ; cout << findSubset ( arr , n , k ) ; return 0 ; }