Efficiently multiply (n-1) elements of an array
c, c++, performance
Solution
Without spoiling too much, you should try and use two variables to store the result of the multiplications: both the cumulative result of the multiplications on the left of the i'th element and on the right of the i'th element.
Problem
Possible Duplicate: Interview Q: given an array of numbers, return array of products of all other numbers (no division) I have two arrays `inputArray` and `resultArray` having `n` elements each. The task is that the nth element in `resultArray` should have the multiplication of all elements in `inputArray` except the nth element of `inputArray` (`n-1` elements in all). eg. `inputArray={1,2,3,4}` then `resultArray={24,12,8,6}` This is easy... ``` for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(i != j) resultArray[i] *= inputArray[j]; ``` But the problem is that the complexity shouldn't exceed O(n) Also we are not allowed to use division. How do I solve this?