CODEWITHSUNDEEP
algorithmcombinations
biswas N
biswas N

Reputation: 381

Sum of Product of All Possible Combinations in an Array

There is an array of N elements. I have to choose K elements and multiply them, say the value of multiplication is M(k). Now add all possible M(k). Say the sum is S(k). Is it possible to determine all the values of S(k) (where 1 <= k <= N) in time-complexity of O(N^2)?

There is a solution in this forum in Python language but I don't know Python and beside this I want this problem to be solved generally.

Upvotes: 0

Views: 1208

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

Basically what you want is to expand the product of monomials

(1 + A[0] x) (1 + A[1] x) ... (1 + A[N-1] x)

and read off the coefficients of x, x^2, ..., x^N. There's an easy O(N^2)-time solution that uses the school algorithm to multiply in each factor one by one.

Upvotes: 3

Related Questions