class Solution:
    def fib(self, n: int) -> int:
        # 0 1 2 3 4 5 6
        # 0 1 1 2 3 5 8
        #return self.fib_r(n)
        return self.fib_a(n)
    
    def fib_a(self, n:int) -> int:
        # Time Complexity: O(n)
        # Space Complexity: O(1)
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        prevF = 0
        prevL = 1
        i = 2
        
        while i <= n:
            x = prevF + prevL
            prevF, prevL = prevL, x
            i += 1
            
        return prevL
        
    def fib_slow(self, n: int) -> int:
        # Time Complexity: O(n)
        # Space Complexity: O(n * n)
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        return self.fib_r(n - 1) + self.fib_r(n - 2)
        
    def fib_r(self, n: int) -> int:
        # Time Complexity: O(n)
        # Space Complexity: O(n)
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        def _fib(n: int) -> [int]:
            if n == 1:
                return 0, 1
            
            a, b = _fib(n - 1)
            return b, (a + b)
            
        a, b = _fib(n)    
        return b