nore

Actually, it turns out my proof is incorrect. I'd be interested if anyone has a correct proof, it looks like this question is actually quite classic (there are a few other copies of it in other stackexchange sites, and it seems to be asked quite often at job interviews), but I have not been able to find any proof of a lower bound on the number of operations needed.

@user2357112 you are right, I assumed we didn't need addition and subtraction. I think I have a proof for that as well, so I am updating the post.

The third multiplication saved is the one whose result was the production of all other elements, since you never need to compute that full product of all the elements.

I believe that 3(n-2) multiplications is a lower bound on the number of operations needed, which I have not yet been able to prove however, only being able to prove the weaker 2(n-2) lower bound. Has anyone an idea on how to prove it?

The left and right arrays do not compute the full product, hence they cost only 998 each.

@Lembik Indeed, that line was probably added afterwise. I'll update the code to take care of that.

@Lembik If you want floats instead, just change int to float. Actually, the first line is only needed if you want a full program; you don't need it if you define the list using another way.