# Daily coding problem #2: Product in Array

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:

``````def product(list):
p = 1
for i in list:
p *= i
return p

def get_product(l):
p = product(l)

return [p // e for e in l]
``````

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:

``````def products(list):
p = 1
pn = 1
nz = 0
for i in list:
p *= i
if i != 0:
pn *= i
else:
nz += 1
return (p, pn, nz)

def get_product(l):
p, pn, nz = products(l)

if nz==0:
return [p // e for e in l]
elif nz==1:
return [(p // e if e!=0 else pn) for e in l]
else:
return [0 for _ in l]
``````

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:

``````def get_product_no_division(l):
return [product(list(l[:i] + l[i+1:])) for i in range(0,len(l))]
``````

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

## Test unit

``````import unittest
import re
from product import get_product, get_product_no_division

tests = [
{'test': [1, 2, 3, 4, 5], 'result': [120, 60, 40, 30, 24]},
{'test': [3, 2, 1], 'result': [2, 3, 6]},
{'test': [0, 1, 2], 'result': [2, 0, 0]},
{'test': [0, 0, 1], 'result': [0, 0, 0]},
]

class TestStringMethods(unittest.TestCase):

def test_get_product(self):
for t in tests:
self.assertEqual(get_product(t['test']), t['result'])

def test_get_product_no_division(self):
for t in tests:
self.assertEqual(get_product_no_division(t['test']), t['result'])

def test_compare_products(self):
for t in tests:
print(t['test'])
self.assertEqual(get_product(t['test']), get_product_no_division(t['test']))

if __name__ == '__main__':
unittest.main()
``````
Written on February 13, 2019