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:
Solutions
Solution 1: Recurrence
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).
PythonJavaC++GoTypeScriptRustJavaScriptPHP
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a(code-box)
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;
}
}(code-box)
class Solution {
public:
int fib(int n) {
int a = 0, b = 1;
while (n--) {
int c = a + b;
a = b;
b = c;
}
return a;
}
};(code-box)
func fib(n int) int {
a, b := 0, 1
for i := 0; i < n; i++ {
a, b = b, a+b
}
return a
}(code-box)
function fib(n: number): number {
let [a, b] = [0, 1];
while (n--) {
[a, b] = [b, a + b];
}
return a;
}(code-box)
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
}
}(code-box)
/**
* @param {number} n
* @return {number}
*/
var fib = function (n) {
let [a, b] = [0, 1];
while (n--) {
[a, b] = [b, a + b];
}
return a;
};(code-box)
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;
}
}(code-box)
Solution 2: Matrix Exponentiation
We define Fib(n) as a 1 × 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 Fib(n) from Fib(n - 1) = \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix}. In other words, we need a matrix base such that Fib(n - 1) × base = 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 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 base^{n}. We can solve this using matrix exponentiation.
The time complexity is O(log n), and the space complexity is O(1).
PythonJavaC++GoTypeScriptRustJavaScript
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](code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}(code-box)
/**
* @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;
}(code-box)
