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]))
```

What if we wanted to write a python function named `zeroSumSlice()`

that:

- Takes any list of integers as an argument.
- 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]))
```

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)
```

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.
```

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.
```

`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]))
```

What is the time complexity of `betterZeroSumSlice`

from question 4?

In [ ]:

```
# YOUR ANSWER HERE. Use Big-O notation.
```

Write your own version of `zeroSumSlice`

that is as fast as possible.

In [ ]:

```
def bestZeroSumSlice(lst):
# YOUR CODE HERE
return
```

What is the time complexity of `bestZeroSumSlice`

?

In [ ]:

```
# YOUR ANSWER HERE. Use Big-O notation.
```