8. Product of Array Except Self

Difficulty: medium · Array, Prefix Sum

Problem

Given an integer array `nums`, print an array `answer` where `answer[i]` is the product of every element of `nums` **except** `nums[i]`. Solve it in O(n) time **without using division**.

Input

The first line holds `n`. The second holds `n` integers.

Output

Print `answer`, space separated.

Example 1

Input:
4
1 2 3 4
Output:
24 12 8 6

Explanation: For example, answer[0] is the product of everything after index 0: 2 × 3 × 4 = 24.

Example 2

Input:
5
-1 1 0 -3 3
Output:
0 0 9 0 0

Explanation: Only the position of the single zero gets a non-zero product; every other product includes that zero.

Example 3

Input:
2
5 7
Output:
7 5

Explanation: For example, answer[0] is the product of everything after index 0: 7 = 7.

Example 4

Input:
3
0 0 2
Output:
0 0 0

Explanation: There are at least two zeroes, so every product includes a zero.

Example 5

Input:
4
2 2 2 2
Output:
8 8 8 8

Explanation: For example, answer[0] is the product of everything after index 0: 2 × 2 × 2 = 8.

Example 6

Input:
5
1 -1 1 -1 1
Output:
1 -1 1 -1 1

Explanation: For example, answer[0] is the product of everything after index 0: -1 × 1 × -1 × 1 = 1.

Example 7

Input:
3
10 -2 3
Output:
-6 30 -20

Explanation: For example, answer[0] is the product of everything after index 0: -2 × 3 = -6.

Example 8

Input:
6
1 2 0 4 5 6
Output:
0 0 240 0 0 0

Explanation: Only the position of the single zero gets a non-zero product; every other product includes that zero.

Example 9

Input:
5
3 -2 -2 -5 -3
Output:
60 -90 -90 -36 -60

Explanation: For example, answer[0] is the product of everything after index 0: -2 × -2 × -5 × -3 = 60.

Example 10

Input:
5
-2 -2 -2 4 -1
Output:
-16 -16 -16 8 -32

Explanation: For example, answer[0] is the product of everything after index 0: -2 × -2 × 4 × -1 = -16.

Constraints

- 2 <= n <= 10^5 - -30 <= nums[i] <= 30 - Every prefix and suffix product fits in a 32-bit signed integer.

Solutions are judged against 10 sample and 5 hidden tests. Sign in to solve it · All problems