Fibonacci Number

XXX. Fibonacci Number

Dynamic Programming

Iterative

Problem Statement:

Given an integer N, calculate the Nth Fibonacci number using an iterative approach. The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(N) = F(N - 1) + F(N - 2) for N > 1

Algorithm:

1. Handle the base cases:
   • Return N directly if N <= 1.
   • Return 1 if N == 2.
2. Use three variables:
   • current: Tracks the current Fibonacci number.
   • prev1: Tracks F(N-1).
   • prev2: Tracks F(N-2).
3. Iterate from 3 to N:
   • Update current as the sum of prev1 and prev2.
   • Shift prev2 to prev1, and prev1 to current.
4. Return current as the result.

Complexity:

Time: O(N) – The loop runs from 3 to N.
Space: O(1) – Only a constant amount of extra space is used.

Java Implementation:

public int fib(int N) {
    if (N <= 1) return N; // Handle base cases
    if (N == 2) return 1; // Special case for N = 2

    int current = 0; // Tracks the current Fibonacci number
    int prev1 = 1;   // Tracks F(N-1)
    int prev2 = 1;   // Tracks F(N-2)

    for (int i = 3; i <= N; i++) {
        current = prev1 + prev2; // Calculate the current Fibonacci number
        prev2 = prev1;           // Shift F(N-1) to F(N-2)
        prev1 = current;         // Shift current to F(N-1)
    }

    return current; // Return the Nth Fibonacci number
}
                

Python Implementation:

def fib(N):
    if N <= 1:
        return N  # Base case
    if N == 2:
        return 1  # Special case for N = 2

    current, prev1, prev2 = 0, 1, 1  # Initialize variables

    for _ in range(3, N + 1):
        current = prev1 + prev2  # Calculate current Fibonacci number
        prev2 = prev1            # Shift F(N-1) to F(N-2)
        prev1 = current          # Shift current to F(N-1)

    return current  # Return the Nth Fibonacci number
                

C++ Implementation:

int fib(int N) {
    if (N <= 1) return N; // Handle base cases
    if (N == 2) return 1; // Special case for N = 2

    int current = 0; // Tracks the current Fibonacci number
    int prev1 = 1;   // Tracks F(N-1)
    int prev2 = 1;   // Tracks F(N-2)

    for (int i = 3; i <= N; ++i) {
        current = prev1 + prev2; // Calculate the current Fibonacci number
        prev2 = prev1;           // Shift F(N-1) to F(N-2)
        prev1 = current;         // Shift current to F(N-1)
    }

    return current; // Return the Nth Fibonacci number
}