Iam_Sandeep

Count all subsequences whose product is less than K

May 2nd, 2022
1,255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.05 KB | None | 0 0
  1. def countSubsequences(a, n, p):
  2.     dp={}
  3.     '''
  4.     We shall create a dp of size K*N k is given product.
  5.     Each cell (x,y) in dp tells that how many subsequences are possible whose
  6.     product <=k by choosing first y elements
  7.     '''
  8.     def help(i,cur):
  9.        
  10.         if cur==0 or i<0:return 0
  11.         if (i,cur) in dp:return dp[(i,cur)]
  12.         ans=0
  13.         '''
  14.         cur:current product
  15.         i:first i elements of array a
  16.         Now we are taking all the subsequence of previous cell
  17.         since these are also the answers. And we shall add
  18.         more subsequence if we found something new
  19.         '''
  20.         ans+=help(i-1,cur)
  21.  
  22.         if a[i]<=cur and a[i]>0:
  23.             ans+=help(i-1,cur//a[i])+1
  24.         '''
  25.         We shall add 1 extra subsequence which is new {a[i]} .We shall add.
  26.         Now we shall check the new subsequences with this a[i].
  27.         so we shall compute (i-1,cur//a[i]). Here first parameter is i-1
  28.         because we are computing it for first i vals of array.
  29.         we shall count the subsequences of cur//a[i] that can be added to our a[i] and
  30.         add this count to our answer
  31.         '''
  32.         dp[(i,cur)]=ans
  33.         return ans
  34.     return help(n-1,p)
Advertisement
Add Comment
Please, Sign In to add comment