n numbers in an array (you can't assume they are integers), I would like to compute the product of all subsets of size
You can do this by multiplying all the numbers together and then dividing by each one in turn, as long as none of the numbers is zero. However, how quickly can you do this with no division?
If you don't allow division, what is the minimum number of arithmetic operations (e.g. multiplication and addition) needed to compute the product of all subsets of size n-1?
Clearly you can do it in
To clarify, the output is
n different products and the only operations apart from reading and writing to memory allowed are multiplication, addition and subtraction.
If the input has three numbers
2,3,5, then the output is three numbers
15 = 3*5,
10 = 2*5 and
6 = 2*3.
Answers should give an exact formula for the number of arithmetic operations their code will use in terms of
n. To make life simple, I will just plug
n = 1000 into your formula to judge its score. The lower the better.
If it's too hard to produce an exact formula for your code, you can just run it for
n = 1000 and count the arithmetic operations in the code. An exact formula would be best however.
You should add your score for
n=1000 to your answer for easy comparison.