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):
    # YOUR CODE HERE
    return

Question 7

What is the time complexity of bestZeroSumSlice?

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