CODEWITHSUNDEEP
algorithm
Sunny
Sunny

Reputation: 381

Finding the value of a sum over all the subsets of a given set

Given a sequence A={a1,a2,a3,…,an} we have to find the

Summation of Length*(All the subsequence product)

For EX:
A= {1 2}
There are 3 sub sequences = {1} , {2} , {1,2}
S = 1*(1) + 1*(2) + 2*(1*2)
  = 1+2+4= 7

Similarly for A={1,2,3} we have S=46.

Is there an efficient way to compute this quantity, as each element will appear 2^n−1 times ?

Upvotes: 1

Views: 54

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Yes, in linear time.

Let

f(x) = (1 + a1*x) * (1 + a2*x) * … * (1 + an*x).

We have

        n
f(x) =  ∏  (1 + aj*x)
       j=1

     =       ∑          ∏   aj*x.
       S ⊂ {1, …, n}  j ∈ S

Letting f' be the derivative of f with respect to x,

                             |S|-1
f'(x) =       ∑       |S| * x      *   ∏   aj,
        S ⊂ {1, …, n}                j ∈ S

so the answer is f'(1).

The Python code below works incrementally, where f is the value of f(1), and df is the value of f'(1). The update for df uses the product rule for derivatives.

def answer(A):
    f, df = (1, 0)
    for a in A:
        # multiply by (1 + a*x), at x=1
        f, df = (f * (1 + a), df * (1 + a) + f * a)
    return df

Upvotes: 1

Related Questions