My in-place $O(nlogn)$ time, $O(logn)$ additional space solution
Let $a = <a_1, ..., a_n>$.
Define the function $\operatorname{f}(\texttt{start}, \texttt{end}) : \texttt{int}$. $\texttt{start}$ and $\texttt{end}$ define the inclusive start and end indices in $a$. The function returns the product of all elements in the range. $\operatorname{f}(1, n)$ updates $a$ in-place to the desired result.
Define $\texttt{length} = (\texttt{end} - \texttt{start}) + 1$. Run the appropriate of the following alternatives:
- If $\texttt{length} = 1$, set $a_{start} = 1$ and return the original $a_{start}$.
- If $\texttt{length} = 2$, swap $a_{start}$ and $a_{end}$ and return their product.
- If $\texttt{length} > 2$:
- Set $\texttt{leftEnd} = \operatorname{floor}(\texttt{length} /2)$.
- Set $\texttt{productLeft} = \operatorname{f}(\texttt{start}, \texttt{leftEnd})$.
- Set $\texttt{productRight} = \operatorname{f}(\texttt{leftEnd} + 1, \texttt{end})$.
- For $i \in [\texttt{start}, \texttt{leftEnd}]$, replace $a_i$ with $a_i * \texttt{productRight}$,
- For $i \in [\texttt{leftEnd} + 1, \texttt{end}]$, replace $a_i$ with $a_i * productLeft$. Return $\texttt{productLeft} * \texttt{productRight}$.
Complexity: At each level of recursion, we call $\operatorname{f}$ once on each half of the input, and then we multiply each half with the product from the other half. This gives $O(nlog(n))$ time. The maximum allocation size at each call level is $O(1)$, and there are $log(n/2)$ levels of recursion, so this means $O(log(n))$ additional space allocation.
int
s. You could do what you propose with shifting, which is not specifically disallowed, but I don't think that it would follow the spirit of the question. More importantly, I've just re-read the question, and I've realised that I made a big mistake: You are meant to create a new array while leaving the original intact. I'm not really sure what to do about this. I might ask on meta. Therefore Vince's answer wins with a slight modification. $\endgroup$