Fastest Method for Find Multiplication Array ( by Minimum Number of Operations)

Question

An interview question:

I have an array: for example this one:

a,b,c,d,e,f,g!=0

List_1=[a,b,c,d,e,f,g]

and I wan to find an optimum method with least operators to find this result:

Multiplication=[a+bcdefg,ab+cdefg,abc+defg,abcd+efg,abcde+fg,abcdef+g]

I propose to use this method:

mult=a*b*c*d*e*f*g
Multiplication=[]
Temp=List_1[0]
while(i<(len(List_1))-1):
    mult/=List_1[i]
    Multiplication.append(Temp+mult)
    Temp*=List_1[i+1]

This line mult=a*b*c*d*e*f*g take n-1 multiplication, while loop take n-1 multiplication, n-1 division and n-1 addition. So overall time is approximately 3n-3 multiplication and n-1 addition.

Is this simplest method or there are other methods with minimum memory and time?

Answer 1

Create [a, ab, abc, …] first:

l = [a, b, c, d, e, f, g]
result = []
p = 1

for i in range(0, len(l) - 1):
    p *= l[i]
    result.append(p)

Then add […, efg, fg, g] to it:

p = 1

for i in range(len(l) - 1, 0, -1):
    p *= l[i]
    result[i - 1] += p

This takes 2(n − 1) multiplications and n − 1 additions of list elements, which is better than 2(n − 1) multiplications, n − 1 divisions, and n − 1 additions.

It’s also what Primusa described.