Product of Array Except Self

MediumArrays

Open on LeetCodeAmazonAppleGoogleMetaMicrosoft

Given an array, produce a new array where each position holds the product of every element except the one at that position. You must do it without the division operator and in linear time.

Input format (stdin): the first line has n. The second line has n integers. Output the n results separated by spaces.

Examples

Input: 4 1 2 3 4

Output: 24 12 8 6

Position 0 is 2*3*4=24, position 1 is 1*3*4=12, and so on.

Input: 5 -1 1 0 -3 3

Output: 0 0 9 0 0

Any position other than the zero gets a factor of 0.

Constraints

2 <= n <= 10^5
-30 <= nums[i] <= 30
The full answer fits in a 32-bit integer

Sheets

Blind 75NeetCode 150NeetCode 250Striver A2Z

product-of-array-except-self.cpp3 sample tests

Loading editor

Test results

Run the sample tests to check your solution against expected output.

Custom input (stdin)

Output

Run your code to see its output.