FIBONACCI NUMBER

Leetcode Problem #509

Problem statement

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

JAVA CODE FIBONACCI NUMBER

Recursion solution for Fibonacci Number

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        return fib(n-1) + fib(n-2);
    }
}

Complexity issue

• This function uses recursion to compute the Fibonacci number at the nth position.
• Note that this implementation has an exponential time complexity and is not efficient for large n due to repeated calculations.
• For larger inputs, consider using iterative solutions or memoization to optimize the computation.

Iteration solution for Fibonacci Number

• It avoids the overhead of repeated function calls.
• Time Complexity: O(n)
• Space Complexity: O(1)

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1){
            return n;
        }

        int a = 0, b=1, c=0;
        for (int i = 2; i<=n; i++){
            c = a + b;
            a = b;
            b = c;
        }

        return c;
    }
}

Memoization solution for Fibonacci Number

• Memoization stores the results of expensive function calls and reuses the stored results, when the same inputs occur again.
• This technique is particularly useful in Dynamic Programming (DP).
• Time Complexity: O(n)
• Space Complexity: O(n) (due to the map storing intermediate results)

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map <Integer, Integer> mem = new HashMap<>();
    public int fib(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        if (mem.containsKey(n)) {
            return mem.get(n);
        }  
        
        int result = fib(n-1) + fib(n-2);
        mem.put(n, result);
        return result;
    }
}

Both of these approaches are more efficient than the naive recursive solution, especially for large values of n.

Visit Previous Problem#1

Visit Previous Problem#2

Similar Questions

• Climbing Stairs
• Split Array into Fibonacci Sequence
• Length of Longest Fibonacci Subsequence
• N-th Tribonacci Number