Easy but not understand math behind it

Factor 1,2,4 sum of product of substring

How to solve this in O(no. Of factors)

Problem Link please

for each factor, add 1 to it and then multiply. so you get expression
(a+1). (b+1) . (c+1) . … (n+1) upto n factors
if u observe carefully, you’ll see it contains all combinations of a,b,c,… n since to get just ‘a’ , you can multiply it with all other 1s.

Also how we got this?
Its just a polynomial (x+a).(x+b). … (x+n) where a,b,…n are factors and putting x=1 we get all the sum of all coefficients of this polynomial.
all coefficients contacts all the possible combination there are or the power set of all factors.

1 Like

One more thing: Subtract the extra 1 produce due = (1 * 1 * 1 * 1…)

1 Like