Product of All Other Numbers

list_products.py

from functools import reduce
import unittest


def multiply(int_list):
    return reduce(lambda x, y: x*y, int_list)


# O(n^2)
def get_products_of_all_ints_except_at_index(int_list):
    # Make a list with the products
    products = []
    if not isinstance(int_list, list) or len(int_list) < 2:
        raise ValueError('Must provide a list of at least 2 integers.')
    
    for i in xrange(len(int_list)):
        copy = int_list[::]
        copy.pop(i)
        products.append(multiply(copy))

    return products


# O(n) with division
def get_products_of_all_ints_except_at_index(int_list):
    if not isinstance(int_list, list) or len(int_list) < 2:
        raise ValueError('Must provide a list of at least 2 integers.')
        
    # Return all zeroes for lists with > 1 zero
    if int_list.count(0) > 1:
        return [0] * len(int_list)
    
    # For lists with 1 zero, return all zeroes except the index of the 0
    if int_list.count(0) == 1:
        zero_index = int_list.index(0)
        products = [0] * len(int_list) # Fill same-size list with 0s
        copy = int_list[::]
        copy.pop(zero_index)
        products[zero_index] = multiply(copy)
        return products
    
    remaining_product_left = 1
    remaining_product_right = multiply(int_list[1:])

    products = [remaining_product_right]

    for i in xrange(len(int_list)):
        if i == 0:
            continue
        current_int = int_list[i]
        remaining_product_left *= int_list[i-1]
        remaining_product_right /= current_int
        products.append(remaining_product_left * remaining_product_right)

    return products
    

# O(n) without division
def get_products_of_all_ints_except_at_index(int_list):
    if not isinstance(int_list, list) or len(int_list) < 2:
        raise ValueError('Must provide a list of at least 2 integers.')
    
    remaining_product_left = 1
    right_products = [1]
    
    # populate right_products
    running_product_right = 1
    for i in xrange(len(int_list) - 1):
        previous_int = int_list[(i + 1) * -1] # Get the opposite side previous index
        running_product_right *= previous_int
        right_products = [running_product_right] + right_products

    products = [right_products[0]]

    for i in xrange(len(int_list)):
        if i == 0:
            continue
        current_int = int_list[i]
        remaining_product_left *= int_list[i-1]
        products.append(remaining_product_left * right_products[i])

    return products


# Tests

class Test(unittest.TestCase):

    def test_small_list(self):
        actual = get_products_of_all_ints_except_at_index([1, 2, 3])
        expected = [6, 3, 2]
        self.assertEqual(actual, expected)

    def test_longer_list(self):
        actual = get_products_of_all_ints_except_at_index([8, 2, 4, 3, 1, 5])
        expected = [120, 480, 240, 320, 960, 192]
        self.assertEqual(actual, expected)

    def test_list_has_one_zero(self):
        actual = get_products_of_all_ints_except_at_index([6, 2, 0, 3])
        expected = [0, 0, 36, 0]
        self.assertEqual(actual, expected)

    def test_list_has_two_zeros(self):
        actual = get_products_of_all_ints_except_at_index([4, 0, 9, 1, 0])
        expected = [0, 0, 0, 0, 0]
        self.assertEqual(actual, expected)

    def test_one_negative_number(self):
        actual = get_products_of_all_ints_except_at_index([-3, 8, 4])
        expected = [32, -12, -24]
        self.assertEqual(actual, expected)

    def test_all_negative_numbers(self):
        actual = get_products_of_all_ints_except_at_index([-7, -1, -4, -2])
        expected = [-8, -56, -14, -28]
        self.assertEqual(actual, expected)

    def test_error_with_empty_list(self):
        with self.assertRaises(Exception):
            get_products_of_all_ints_except_at_index([])

    def test_error_with_one_number(self):
        with self.assertRaises(Exception):
            get_products_of_all_ints_except_at_index([1])


unittest.main(verbosity=2)