Skip to content

509. Fibonacci Number

Description

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

 

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.

 

Constraints:

  • 0 <= n <= 30

Solutions

Solution 1: Recurrence

Thinking

Fibonacci obeys \(F_n = F_{n-1} + F_{n-2}\). Naive recursion recomputes the same subproblems. Even though \(n \le 30\), an iterative recurrence is enough.

Roll two variables for consecutive terms and iterate \(n\) times. Time is linear and extra space is constant.

We define two variables \(a\) and \(b\), initially \(a = 0\) and \(b = 1\).

Next, we perform \(n\) iterations. In each iteration, we update the values of \(a\) and \(b\) to \(b\) and \(a + b\), respectively.

Finally, we return \(a\).

The time complexity is \(O(n)\), where \(n\) is the given integer. The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int fib(int n) {
        int a = 0, b = 1;
        while (n-- > 0) {
            int c = a + b;
            a = b;
            b = c;
        }
        return a;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int fib(int n) {
        int a = 0, b = 1;
        while (n--) {
            int c = a + b;
            a = b;
            b = c;
        }
        return a;
    }
};

1
2
3
4
5
6
7
func fib(n int) int {
    a, b := 0, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
    }
    return a
}

1
2
3
4
5
6
7
function fib(n: number): number {
    let [a, b] = [0, 1];
    while (n--) {
        [a, b] = [b, a + b];
    }
    return a;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn fib(n: i32) -> i32 {
        let mut a = 0;
        let mut b = 1;
        for _ in 0..n {
            let t = b;
            b = a + b;
            a = t;
        }
        a
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
    let [a, b] = [0, 1];
    while (n--) {
        [a, b] = [b, a + b];
    }
    return a;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function fib($n) {
        $a = 0;
        $b = 1;
        for ($i = 0; $i < $n; $i++) {
            $temp = $a;
            $a = $b;
            $b = $temp + $b;
        }
        return $a;
    }
}

Solution 2: Matrix Exponentiation

Thinking

Solution 1 is already \(O(n)\) and enough here, but the same linear recurrence can be sped up for larger \(n\).

\(F_n\) is a product of a fixed \(2 \times 2\) transition matrix. Fast exponentiation reduces \(n\) multiplications to \(O(\log n)\). The constant is larger; use it when the same recurrence must scale.

We define \(\textit{Fib}(n)\) as a \(1 \times 2\) matrix \(\begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}\), where \(F_n\) and \(F_{n - 1}\) are the \(n\)-th and \((n - 1)\)-th Fibonacci numbers, respectively.

We want to derive \(\textit{Fib}(n)\) from \(\textit{Fib}(n - 1) = \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix}\). In other words, we need a matrix \(\textit{base}\) such that \(\textit{Fib}(n - 1) \times \textit{base} = \textit{Fib}(n)\), i.e.:

\[ \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix} \times \textit{base} = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix} \]

Since \(F_n = F_{n - 1} + F_{n - 2}\), the first column of the matrix \(\textit{base}\) is:

\[ \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]

The second column is:

\[ \begin{bmatrix} 1 \\ 0 \end{bmatrix} \]

Thus, we have:

\[ \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix} \times \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix} \]

We define the initial matrix \(res = \begin{bmatrix} 1 & 0 \end{bmatrix}\), then \(F_n\) is equal to the second element of the first row of the result matrix obtained by multiplying \(res\) with \(\textit{base}^{n}\). We can solve this using matrix exponentiation.

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import numpy as np


class Solution:
    def fib(self, n: int) -> int:
        factor = np.asmatrix([(1, 1), (1, 0)], np.dtype("O"))
        res = np.asmatrix([(1, 0)], np.dtype("O"))
        while n:
            if n & 1:
                res = res * factor
            factor = factor * factor
            n >>= 1
        return res[0, 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int fib(int n) {
        int[][] a = {{1, 1}, {1, 0}};
        return pow(a, n)[0][1];
    }

    private int[][] mul(int[][] a, int[][] b) {
        int m = a.length, n = b[0].length;
        int[][] c = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < b.length; ++k) {
                    c[i][j] = c[i][j] + a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }

    private int[][] pow(int[][] a, int n) {
        int[][] res = {{1, 0}};
        while (n > 0) {
            if ((n & 1) == 1) {
                res = mul(res, a);
            }
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int fib(int n) {
        vector<vector<int>> a = {{1, 1}, {1, 0}};
        return qpow(a, n)[0][1];
    }

    vector<vector<int>> mul(vector<vector<int>>& a, vector<vector<int>>& b) {
        int m = a.size(), n = b[0].size();
        vector<vector<int>> c(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < b.size(); ++k) {
                    c[i][j] = c[i][j] + a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }

    vector<vector<int>> qpow(vector<vector<int>>& a, int n) {
        vector<vector<int>> res = {{1, 0}};
        while (n) {
            if (n & 1) {
                res = mul(res, a);
            }
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func fib(n int) int {
    a := [][]int{{1, 1}, {1, 0}}
    return pow(a, n)[0][1]
}

func mul(a, b [][]int) [][]int {
    m, n := len(a), len(b[0])
    c := make([][]int, m)
    for i := range c {
        c[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < len(b); k++ {
                c[i][j] = c[i][j] + a[i][k]*b[k][j]
            }
        }
    }
    return c
}

func pow(a [][]int, n int) [][]int {
    res := [][]int{{1, 0}}
    for n > 0 {
        if n&1 == 1 {
            res = mul(res, a)
        }
        a = mul(a, a)
        n >>= 1
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function fib(n: number): number {
    const a: number[][] = [
        [1, 1],
        [1, 0],
    ];
    return pow(a, n)[0][1];
}

function mul(a: number[][], b: number[][]): number[][] {
    const [m, n] = [a.length, b[0].length];
    const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            for (let k = 0; k < b.length; ++k) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

function pow(a: number[][], n: number): number[][] {
    let res = [[1, 0]];
    while (n) {
        if (n & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
impl Solution {
    pub fn fib(n: i32) -> i32 {
        let a = vec![vec![1, 1], vec![1, 0]];
        pow(a, n as usize)[0][1]
    }
}

fn mul(a: Vec<Vec<i32>>, b: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = a.len();
    let n = b[0].len();
    let mut c = vec![vec![0; n]; m];

    for i in 0..m {
        for j in 0..n {
            for k in 0..b.len() {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    c
}

fn pow(mut a: Vec<Vec<i32>>, mut n: usize) -> Vec<Vec<i32>> {
    let mut res = vec![vec![1, 0], vec![0, 1]];

    while n > 0 {
        if n & 1 == 1 {
            res = mul(res, a.clone());
        }
        a = mul(a.clone(), a);
        n >>= 1;
    }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
    const a = [
        [1, 1],
        [1, 0],
    ];
    return pow(a, n)[0][1];
};

function mul(a, b) {
    const m = a.length,
        n = b[0].length;
    const c = Array.from({ length: m }, () => Array(n).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            for (let k = 0; k < b.length; ++k) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

function pow(a, n) {
    let res = [
        [1, 0],
        [0, 1],
    ];
    while (n > 0) {
        if (n & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

Comments