Nth Fibonacci Number

Easy

The Fibonacci numbers are defined as F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n>=2. Given n, return F(n).

Examples

Input	Output
n = 2	1
n = 4	3

Python Solution

def fib(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

JavaScript Solution

function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

Step-by-Step Explanation

Iterative approach: only need the last two values.
Start with a=0, b=1. Each step: a becomes b, b becomes a+b.
After n-1 iterations, b holds F(n).

Complexity Analysis

Time	O(n)
Space	O(1)

Tags

MathDynamic Programming

Related Problems

Climbing Stairs FizzBuzz

All Problems

Two Sum Reverse a String Palindrome Check FizzBuzz Binary Search Reverse Linked List Merge Two Sorted Arrays Valid Parentheses Maximum Subarray (Kadane's Algorithm)Remove Duplicates from Sorted Array Valid Anagram First Unique Character Climbing Stairs Roman to Integer Best Time to Buy and Sell Stock Contains Duplicate Move Zeroes Intersection of Two Arrays Longest Common Prefix