Last active
June 29, 2018 01:56
-
-
Save birkholz/233da53a67030156c0ce777d83d84112 to your computer and use it in GitHub Desktop.
Product of All Other Numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment