Fibonacci number

Math Dynamic Programming Recursion Memoization

73.9% acceptance

Feb 19, 2026

9290

410

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).

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn fib(n: i32) -> i32 {
    if n <= 1 {
      return n;
    }
    let (mut a, mut b) = (0i32, 1i32);
    for _ in 2..=n {
      let c = a + b;
      a = b;
      b = c;
    }
    b
  }
}