Product of everything else
MediumStuck?
Show a hintHide the hint
For each position you need the product of everything to its left and everything to its right. Two passes, one from each end.
The idea behind this problem
Next in this lesson
Running sumFor each position, give the product of every number in the list except the one at that position. Do it without using division.
Worked example#
For [1, 2, 3, 4]:
| position | everything else | product |
|---|---|---|
| 0 | 2, 3, 4 | 24 |
| 1 | 1, 3, 4 | 12 |
| 2 | 1, 2, 4 | 8 |
| 3 | 1, 2, 3 | 6 |
So the answer is [24, 12, 8, 6].
Dividing the total product by each number would be quick, but it breaks the moment the list contains a zero. Instead, note that everything else is everything to the left times everything to the right. Two passes, one in each direction, gives both.
Constraints#
2 <= n <= 100000- The answer always fits in a 64 bit integer
Input
nums is a count then that many integers.
Output
The products, separated by spaces.
Examples
Input
4 1 2 3 4
Output
24 12 8 6
At position 0 the rest are 2, 3 and 4, which multiply to 24.
Input
2 2 3
Output
3 2
Each answer is simply the other number.
Input
3 1 0 3
Output
0 3 0
A zero makes every other answer zero, and the zero's own answer is the rest multiplied.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.