# CSPT 19 Lecture 5
## [Plus One](https://leetcode.com/problems/plus-one/)

class Solution:
    """
    Understand
    [1,2,3] --> [1,2,4]
    [9,9,9] --> [1,0,0,0]
    [0] --> [1]
    Plan
    Iterate through list in reverse and keep track of carry digit
    Add carry to other digits in the number if needed
    After iterating through all digits, if there's still a carry then
    add it to the beginning of the list
    """
    """
    digits = [1,0,0,0]
    carry = 1
    i = -1
    currSum = 10
    carry = 1
    Runtime: O(n)
    Space: O(1)
    """
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1 #since we're adding 1
        i = len(digits) - 1
        while i >= 0:
            currSum = digits[i] + carry
            carry = int(currSum / 10)
            digits[i] = currSum % 10
            i -= 1
        if carry > 0:
            digits.insert(0, carry)
        return digits

## [Pivot Index](https://leetcode.com/problems/find-pivot-index)

class Solution:
    """
    Understand
    [1,7,3,(6),5,6] --> 3
    [1,2,3] --> -1
    [] --> -1
    
    Plan
    [1,7,3,6,5,6]
    rightSum = 11
    leftSum = 11
    Runtime: O(n)
    Space: O(1)
    Keep track of left sum and right sum
    Add previous element to the left sum
    Subtract current element from right sum
    If both are equal, then you're at the pivot element
    Runtime: 
    """
    def pivotIndex(self, nums: List[int]) -> int:
        rightSum = sum(nums) # n
        leftSum = 0
        for i, num in enumerate(nums): # n
            if i - 1 >= 0:
                leftSum += nums[i - 1]
            rightSum -= num
            if leftSum == rightSum:
                return i
        return -1