Number of subsets with product less than k | Python3 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 Code
import bisect NEW_LINE def findSubset ( arr , n , k ) : NEW_LINE INDENT vect1 , vect2 , subset1 , subset2 = [ ] , [ ] , [ ] , [ ] NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if arr [ i ] > k : NEW_LINE INDENT continue NEW_LINE DEDENT if i <= n // 2 : NEW_LINE INDENT vect1 . append ( arr [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT vect2 . append ( arr [ i ] ) NEW_LINE DEDENT DEDENT for i in range ( 0 , ( 1 << len ( vect1 ) ) ) : NEW_LINE INDENT value = 1 NEW_LINE for j in range ( 0 , len ( vect1 ) ) : NEW_LINE INDENT if i & ( 1 << j ) : NEW_LINE INDENT value *= vect1 [ j ] NEW_LINE DEDENT DEDENT if value <= k : NEW_LINE INDENT subset1 . append ( value ) NEW_LINE DEDENT DEDENT for i in range ( 0 , ( 1 << len ( vect2 ) ) ) : NEW_LINE INDENT value = 1 NEW_LINE for j in range ( 0 , len ( vect2 ) ) : NEW_LINE INDENT if i & ( 1 << j ) : NEW_LINE INDENT value *= vect2 [ j ] NEW_LINE DEDENT DEDENT if value <= k : NEW_LINE INDENT subset2 . append ( value ) NEW_LINE DEDENT DEDENT subset2 . sort ( ) NEW_LINE count = 0 NEW_LINE for i in range ( 0 , len ( subset1 ) ) : NEW_LINE INDENT count += bisect . bisect ( subset2 , ( k // subset1 [ i ] ) ) NEW_LINE DEDENT count -= 1 NEW_LINE return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 4 , 2 , 3 , 6 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE k = 25 NEW_LINE print ( findSubset ( arr , n , k ) ) NEW_LINE DEDENT