Fibonacci Number

# Fibonacci Number ## Difficulty Easy ## Tags `recursion`, `dynamic programming`, `math` ## Problem Statement The Fibonacci numbers form a sequence where each number is the sum of the two preceding ones, starting from 0 and 1: ``` F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1 ``` Given `n`, calculate `F(n)`. ## Constraints - 0 ≤ n ≤ 30 ## Signatures ### Python ```python def fib(n: int) -> int: pass ``` ### Java ```java public class Solution { public int fib(int n) { return null; } } ``` ### Csharp ```csharp public class Solution { public int fib(int n) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int fib(int n) { } }; ``` ### C ```c int fib(int n) { } ``` ### Ruby ```ruby def fib(n) end ``` ### Perl ```perl sub fib { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def fib(n: Int): Int = { } } ``` ### Haskell ```haskell fib :: ... -> ... fib args = undefined ``` ### Clojure ```clojure (defn fib [n] ) ``` ### Scheme ```scheme (define (fib n) ) ``` ## Examples ### Example 1 **Input:** ``` n = 2 ``` **Output:** ``` 1 ``` **Explanation:** F(2) = F(1) + F(0) = 1 + 0 = 1 ### Example 2 **Input:** ``` n = 3 ``` **Output:** ``` 2 ``` **Explanation:** F(3) = F(2) + F(1) = 1 + 1 = 2 ### Example 3 **Input:** ``` n = 4 ``` **Output:** ``` 3 ``` **Explanation:** F(4) = F(3) + F(2) = 2 + 1 = 3 ### Example 4 **Input:** ``` n = 10 ``` **Output:** ``` 55 ``` ## Hints 1. **Recursive** (naive): Direct translation of formula, but O(2^n) time. 2. **Memoization**: Store computed values to avoid recomputation, O(n) time/space. 3. **Iterative**: Use two variables to track F(n-1) and F(n-2), O(n) time, O(1) space. 4. **Matrix exponentiation**: O(log n) time for large n.