Consider a list named foo
foo = [2, 3, -2, 1, -2, 5, 1]
Notice how foo[1:5]
, that is, [3, -2, 1, -2]
, sums to zero.
That is, 3 + (-2) + 1 + (-2) = 0.
print('Here is a slice of foo:', foo[1:5])
print('This slice sums to:', sum(foo[1:5]))
Here is a slice of foo: [3, -2, 1, -2] This slice sums to: 0
What if we wanted to write a python function named zeroSumSlice()
that:
Specifically, this function should return any slice that sums to zero,
so long as that slice is not an empty list []
.
If there is no such slice in the list, this function should return None
instead.
zeroSumSlice([1,-3,3,1]) # returns [-3, 3]
zeroSumSlice([1,2,3]) # returns None
Here is one way to write this function.
def zeroSumSlice(lst):
n = len(lst)
# try every possible slice in the list.
# see if any slice sums to zero.
for i in range(n):
for j in range(i + 1, n):
someSlice = lst[i:j]
if sum(someSlice) == 0:
return someSlice
# no slice found
return None
print(zeroSumSlice([2, 3, -2, 1, -2, 5, 1]))
print(zeroSumSlice([1, -3, 3, 1]))
print(zeroSumSlice([1, 2, 3]))
[3, -2, 1, -2] [-3, 3] None
In python, sum()
is a built-in function. Try writing your own mySum()
function to see how it works
# mySum takes a list of numbers, lst, and returns the sum of those numbers.
def mySum(lst):
# YOUR CODE HERE. Use a for loop. Do not use sum()!
return
# If your code is correct,
# these statements should all print True
print(mySum([1, 2, 3]) == 6)
print(mySum(range(100)) == 4950)
print(mySum([]) == 0)
print(mySum([1, -1]) == 0)
False False False False
If we call the length of the list n
, what is the time complexity of mySum()
in terms of n
?
Use asymptotic (Big-O) notation.
# YOUR ANSWER HERE. Use Big-O notation.
Look at the code for zeroSumSlice()
. What is the time complexity of zeroSumSlice()
in terms of the length of the list, n
?
# YOUR ANSER HERE. Use Big-O notation.
zeroSumSlice
is copied below. Make a small change to zeroSumSlice that improves the time complexity. You only need to change a few lines of code.
# CHANGE A FEW LINES of this code to make it faster.
# HINT: remove the sum() call and do something else.
def betterZeroSumSlice(lst):
n = len(lst)
# try every possible slice in the list.
# see if any slice sums to zero.
for i in range(n):
for j in range(i + 1, n):
candidateSlice = lst[i:j]
if sum(candidateSlice) == 0:
return candidateSlice
# no slice found
return None
print(betterZeroSumSlice([2, 3, -2, 1, -2, 5, 1]))
print(betterZeroSumSlice([1, -3, 3, 1]))
print(betterZeroSumSlice([1, 2, 3]))
What is the time complexity of betterZeroSumSlice
from question 4?
# YOUR ANSWER HERE. Use Big-O notation.
Write your own version of zeroSumSlice
that is as fast as possible.
def bestZeroSumSlice(lst):
# YOUR CODE HERE
return
What is the time complexity of bestZeroSumSlice
?
# YOUR ANSWER HERE. Use Big-O notation.