This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Solution Notebook¶
Problem: Given a list of ints, find the products of every other int for each index.¶
Constraints¶
- Can we use division?
- No
- Is the output a list of ints?
- Yes
- Can we assume the inputs are valid?
- No
- Can we assume this fits memory?
- Yes
Test Cases¶
* None -> TypeError * [] -> [] * [0] -> [] * [0, 1] -> [1, 0] * [0, 1, 2] -> [2, 0, 0] * [1, 2, 3, 4] -> [24, 12, 8, 6]
Algorithm¶
Brute force:¶
sum = 1
|
[1, 2, 3, 4]
^
skip if both pointers are pointing to the same spot
|
[1, 2, 3, 4]
^
sum *= 2
|
[1, 2, 3, 4]
^
sum *= 3
|
[1, 2, 3, 4]
^
sum *= 4
results.append(sum)
results = [24]
repeat for every element in the input list to obtain:
[24, 12, 8, 6]
Complexity:
- Time: O(n^2)
- Space: O(n)
Greedy¶
input = [1, 2, 3, 4] result = [2*3*4, 1*3*4, 1*2*4, 1*2*3] Note we are duplicating multiplications with the brute force approach. We'll calculate all products before an index, and all products after an index. We'll then multiple these two together to form the result. input = [1, 2, 3, 4] before = [1, 1, 1*2, 1*2*3] after = [2*3*4, 1*3*4, 1*2*4, 1] result = [ 24, 12, 8, 6]
Complexity:
- Time: O(n)
- Space: O(n)
Code¶
In [1]:
class Solution(object):
def mult_other_numbers_brute(self, array):
if array is None:
raise TypeError('array cannot be None')
if not array:
return array
if len(array) == 1:
return []
result = []
for i in range(len(array)):
curr_sum = 1
for j in range(len(array)):
if i == j:
continue
curr_sum *= array[j]
result.append(curr_sum)
return result
def mult_other_numbers(self, array):
if array is None:
raise TypeError('array cannot be None')
if not array:
return array
if len(array) == 1:
return []
result = [None] * len(array)
curr_product = 1
for i in range(len(array)):
result[i] = curr_product
curr_product *= array[i]
curr_product = 1
for i in range(len(array))[::-1]:
result[i] *= curr_product
curr_product *= array[i]
return result
Unit Test¶
In [2]:
%%writefile test_mult_other_numbers.py
import unittest
class TestMultOtherNumbers(unittest.TestCase):
def test_mult_other_numbers(self):
solution = Solution()
self.assertRaises(TypeError, solution.mult_other_numbers, None)
self.assertEqual(solution.mult_other_numbers([0]), [])
self.assertEqual(solution.mult_other_numbers([0, 1]), [1, 0])
self.assertEqual(solution.mult_other_numbers([0, 1, 2]), [2, 0, 0])
self.assertEqual(solution.mult_other_numbers([1, 2, 3, 4]), [24, 12, 8, 6])
print('Success: test_mult_other_numbers')
def main():
test = TestMultOtherNumbers()
test.test_mult_other_numbers()
if __name__ == '__main__':
main()
Overwriting test_mult_other_numbers.py
In [3]:
%run -i test_mult_other_numbers.py
Success: test_mult_other_numbers