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()