This problem was asked by Uber.
Given an array of integers, return a new array such that each element at index
iof the new array is the product of all the numbers in the original array except the one at
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)