Challenge: Finding slices of lists that sum to zero¶

Consider a list named foo

In [2]:
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.

In [3]:
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:

1. Takes any list of integers as an argument.
2. Returns a slice of that list that sums to zero.

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.

In [1]:
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


Question 1¶

In python, sum() is a built-in function. Try writing your own mySum() function to see how it works

In [5]:
# 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


Question 2¶

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.

In [ ]:
# YOUR ANSWER HERE. Use Big-O notation.


Question 3¶

Look at the code for zeroSumSlice(). What is the time complexity of zeroSumSlice() in terms of the length of the list, n?

In [ ]:
# YOUR ANSER HERE. Use Big-O notation.


Question 4¶

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.

In [ ]:
# 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]))


Question 5¶

What is the time complexity of betterZeroSumSlice from question 4?

In [ ]:
# YOUR ANSWER HERE. Use Big-O notation.


Question 6¶

Write your own version of zeroSumSlice that is as fast as possible.

In [ ]:
def bestZeroSumSlice(lst):

What is the time complexity of bestZeroSumSlice?
# YOUR ANSWER HERE. Use Big-O notation.