SUMMER OF '69: Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 9 (every 6 will be followed by at least one 9). Return 0 for no numbers.
SUMMER OF '69: Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 9 (every 6 will be followed by at least one 9). Return 0 for no numbers.
My solution:
def summer_sum(a_list):
"""
Use a stack to solve the problem.
1. If current num is '6', push '0' on the stack.
2. If current num is not '6' and the stack is empty, add it.
3. If current num is '9' and the stack is not empty, pop the stack.
"""
exclude_stack = []
total = 0
for num in a_list:
if num == 6:
exclude_stack.append(0)
elif not len(exclude_stack):
total += num
elif num == 9 and len(exclude_stack):
exclude_stack.pop()
return total
Questions:
- Is this implementation correct?
- Is the time complexity of the this implementation O(n)?
- Is there a better/faster way to solve the problem?