Return copy of array, each element product of all others, constant additional space, no division Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows:

Given an array $&lt;a_1, \ldots, a_n&gt;$ of fixed-length ints, devise an algorithm which returns a new array $&lt;b_1, \ldots, b_n&gt;$ where each $b_i$ is the product of all $a_j$ with $j \neq i$. That is, each element of the result is the product of all other elements in the original array. Division is not allowed, and the algorithm  must run in $O(n)$ time and $O(1)$ additional space.

Example: $&lt;1, 2, 3&gt;$ should be updated to $&lt;2*3, 1*3, 1*2&gt;$.
A variation of a solution left by a commenter called Vince
Given input $a = &lt;a_1, ..., a_n&gt;$.

Allocate result array $b = &lt;b_1, \ldots, b_n&gt;$. Set $product = 1$.
For $i \in [1, n]$, set $b_i = product$ and set $product = product * a_i$.
Set $product = a_n$. For $i \in [n - 1, 1]$, set $b_i = b_i * product$, and set $product = product * a_i$.
Return the array $&lt;b_1, \ldots, b_n&gt;$.

This solution runs in $O(n)$ time and $O(1)$ space additional to that allocated for the result.