CODEWITHSUNDEEP
algorithmdynamic-programming
Vasiu Alexandru
Vasiu Alexandru

Reputation: 123

How can I count the no. of subsequences that have the product of elements smaller or equal a number D?

How can I count the no. of subsequences of an array that have the product of elements smaller or equal a number D without counting the empty subsequence?

For example :

array=[2,2,2,3,4,10] D=50 The answer should be 39. I tried with backtracking, but it's not so faster. All number in the array are smaller or equal with D and bigger than 0.

Upvotes: 0

Views: 1133

Answers (1)

Sayalic
Sayalic

Reputation: 7650

My solution:

Since D is relatively small, so we change the problem to:

smaller and equal with D => equal with X(X = 1 to D).

The way to solve equal with X:

define f(x,n) = the number of the ways to product to `x` by using first n numbers.

And we will get:

f(x,n) = f(x, n-1) + f(x div a[n], n-1) (if x mod a[n] == 0)

Combining with memorization, we will get a O(D*n) solution.

Here is the code:

__author__ = 'Sayakiss'

global a, mem

#a = [2, 2, 2, 3, 4, 10]
a = [2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 27, 29, 31, 101, 103]
mem = {}

def solve(x):
    sum = 0
    for i in range(1, x + 1):
        sum += f(i, len(a) - 1)
        #print str(i) + " " + str(f(i, len(a) - 1))
    return sum

def f(x, n):
    if x == 1:
        return 1
    if n == -1:
        return 0
    if mem.get((x, n)) is not None:
        return mem.get((x, n))
    result = 0
    if x % a[n] == 0:
        result += f(x / a[n], n - 1)
    result += f(x, n - 1)
    mem[(x, n)] = result
    return result

#print solve(50)
print solve(200000)

PS:

If there is any 1 in array a, my solution will fail. But it's easy to handle that, so you may do it by yourself.

Upvotes: 1

Related Questions