727. The Product of Everything Else

For each position, print the product of ALL the other values.

You may NOT use division.

1 2 3 4 -> 24 12 8 6 0 1 2 -> 2 0 0 0 0 3 -> 0 0 0 7 0 -> 0 7

## Why the rule is there, and not just to be awkward

The obvious idea is "multiply everything, then divide by this value". The ban is not arbitrary.

Zeros break it outright. With 0 1 2 the whole product is 0, and 0 divided by 0 is undefined. The total carries no information about the position holding the zero, which is exactly the position whose answer is non zero.

You can patch that by counting the zeros: none means divide, one means every answer is 0 except at that position, two or more means every answer is 0. That works, and it is three cases where the intended method has none.

And the patch does not travel. The moment the answer has to be taken modulo something, division means a modular inverse, which needs the modulus prime and still cannot rescue the zero. The prefix-and-suffix method carries over unchanged.

Being able to say WHY the obvious approach is rejected, rather than only that it is, is what this question is asked for.

## Prefix and suffix, meeting at each position

Everything except position i is everything to its left times everything to its right:

pre[i] = a[0] * a[1] * ... * a[i-1] with pre[0] = 1 suf[i] = a[i+1] * ... * a[n-1] with suf[n-1] = 1 answer[i] = pre[i] * suf[i]

The EMPTY PRODUCT is 1, and that single convention is what makes both ends work without a special case.

## Two passes, one output array

The left products can be written straight into the output on a forward pass, then multiplied by a running right product on a backward pass. No second array is needed:

run = 1 for i in 0 .. n-1: out[i] = run; run *= a[i] run = 1 for i in n-1 .. 0: out[i] *= run; run *= a[i]

## Zeros need no code at all

A zero appears in one of the two products for every position except its own, so it propagates by itself. With two or more zeros every answer is 0, because every position still has a zero on one side. 0 0 3 giving 0 0 0 with no extra branch is the check that the method is genuinely general rather than patched.

## Boundaries

A single value answers 1, the empty product.

## Overflow

The guarantee is about the product of the NON ZERO values, and that wording is load bearing.

Bounding the product of ALL the values would be useless here: one zero makes that product zero, so the bound is satisfied by any input at all, while the answer at the zero's own position is the product of everything else and can be arbitrarily large. On 1000 1000 1000 1000 1000 1000 1000 0 the whole product is 0 and the answer at the last position is 10^21, which wraps to 3875820019684212736 in a signed 64 bit integer.

Bounding the non zero product fixes it, because every prefix and every suffix product divides that number and therefore fits whenever it does.

In JavaScript the products exceed 2^53 long before they reach the 64 bit ceiling, so the arithmetic needs big integers regardless.

## Cost

Time O(n). Space O(1) beyond the output.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each value ≤ 1000` - the product of all the NON ZERO values fits in a signed 64 bit integer