Problem:

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can’t use division?

There’s a simple solution, which unfortunately would not cover all edge cases:

• calculate the product of all elements in the input array
• return a new array, where the new element at the n-position is the product calculated at the previous step, divided by the element at the n-position

for example, if our input is [1, 2, 3, 4, 5] the product is 1 * 2 * 3 * 4 * 5 = 120 and the result is [120 // 1, 120 // 2, 120 // 3, 120 // 4, 120 // 5] = [120, 60, 40, 30, 24] and the python code to obtain this result would be:

But if we allow any element to assume the value of zero we have to handle some special cases:

Exactly one element is zero

If the element at the n-th position is zero, then we have to return an array of all zeroes, except the one at the n-th position which is the product of all non zeroes elements.

More than one element is zero

We have to return an array of all zeroes.

This is a slight modification to the code, in order to handle such situations:

products will return:

• the product of all elements
• the product of all non zero elements
• the number of zero elements

once we have those three values we can calculate the resulting array:

• if there are no zeroes, return the product p divided by the current element e
• if there’s exactly one zero, handle the special case
• if there are more zeroes, return all zeroes.

Without using the division

There’s no need do handle any special case:

(but of course the array would be read multiple times)