See the original problem on HackerRank.
Given an array of \( n \) integers where \( n > 1 \), \( nums \), print an array \( output \) such that \( output[i] \) is equal to the product of all the elements of \( nums \) except \( nums[i] \).
Solve the problem in \( O(N) \) without using division.
Input Format
Integer \( n \) denoting the number of elements followed by \( n \) spaceseparated integers  \( nums \). \( 0 < nums[i] < 20 \)
Constraints
\( i < n < 10 \)
Output Format
\( n \) integers (an array \( output \) such that each \( output[i] \) is equal to the product of all the elements of except \( nums[i] \)).
Sample Input


Sample Output


Solutions
This problem is interesting because of two constraints:
 Linear time complexity
 No division can be used
We can solve this problem in two linear steps, by using an additional vector (the red one, in the following figure):
The idea is to keep a “prefix product” from the first element of the input vector, starting writing at the second position of the support vector. Then we do the same in the opposite way.
Here is the code. partial_sum
is a C++ function performing a
prefixsumlike scan, open to any “sum” operation:


To show the prefixsum pattern, here is a very compact solution using another $O(N)$ support vector:


Rust solution, imperative style.


Solution without extra space
We can use logarithm properties:
\( x = a \cdot b \cdot c \)
\( Log(x) = Log(a \cdot b \cdot c) \)
\( Log(x) = Log(a) + Log(b) + Log(c) = sum \)
\( x = 10^{sum} \)
\( \dfrac{x}{a} = 10^{sum  Log(a)} \)


Rounding can be an issue of this solution. It’s a compromise to take into account.
Credits of this solution: https://www.geeksforgeeks.org/productarraypuzzleset2o1space/