Taro Logo

Fibonacci Number

Easy
Google logo
Google
2 views
Topics:
Dynamic ProgrammingRecursion

You are given the following problem:

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). Let's look at some examples:

  • Example 1: If n = 2, the expected output is 1 because F(2) = F(1) + F(0) = 1 + 0 = 1.
  • Example 2: If n = 3, the expected output is 2 because F(3) = F(2) + F(1) = 1 + 1 = 2.
  • Example 3: If n = 4, the expected output is 3 because F(4) = F(3) + F(2) = 2 + 1 = 3.

Write a function that takes an integer n as input (where 0 <= n <= 30) and returns the nth Fibonacci number.

How would you implement this function, and what are the time and space complexities of your solution? Also, consider any edge cases that might be encountered.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the expected data type and range for the input 'n' (e.g., is it a non-negative integer, and what is its maximum possible value)?
  2. Should I handle cases where 'n' is zero or one specifically?
  3. What is the expected return type: should I return an integer, a string, or something else?
  4. Should I be concerned about integer overflow for large values of 'n' and, if so, how should I handle it?
  5. Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

The Fibonacci sequence is a series of numbers where each number is the sum of the two numbers before it. The brute force approach directly applies the definition to calculate the sequence, without trying to optimize the calculation process.

Here's how the algorithm would work step-by-step:

  1. If you need to find the first or second Fibonacci number, the answer is simply one.
  2. For any other Fibonacci number, find the two numbers immediately before the one you are looking for.
  3. Add those two numbers together.
  4. The result of this addition is the Fibonacci number you're trying to find.

Code Implementation

def fibonacci_brute_force(number_to_find):
    # Base cases: first and second Fibonacci numbers are 1
    if number_to_find <= 2:
        return 1

    # Recursively calculate the Fibonacci number.
    previous_fibonacci_number = fibonacci_brute_force(number_to_find - 1)

    penultimate_fibonacci_number = fibonacci_brute_force(number_to_find - 2)

    # The fibonacci number is the sum of the prior two.
    return previous_fibonacci_number + penultimate_fibonacci_number

Big(O) Analysis

Time Complexity
O(2^n)The brute force approach to calculating the nth Fibonacci number involves recursively calling the function for (n-1) and (n-2). This leads to a call tree where each node spawns two more nodes, effectively doubling the number of computations with each level of recursion. The depth of this tree is proportional to n, resulting in approximately 2^n operations. Therefore, the time complexity is O(2^n).
Space Complexity
O(N)The plain English explanation describes a recursive approach. Each call to find a Fibonacci number triggers two more calls (step 2). In the worst-case scenario, to calculate the Nth Fibonacci number, the recursion will go N levels deep. Each level adds a new frame to the call stack, so the auxiliary space used by the call stack grows linearly with N. This means the auxiliary space is O(N).

Optimal Solution

Approach

To find a specific Fibonacci number quickly, we avoid recalculating values we've already found. Instead, we store previously computed Fibonacci numbers and reuse them as needed, building up to the number we're looking for.

Here's how the algorithm would work step-by-step:

  1. Realize that each Fibonacci number is simply the sum of the two numbers before it.
  2. Start with the first two Fibonacci numbers, which are 0 and 1.
  3. To find the next Fibonacci number, just add the previous two. Store this new value.
  4. Repeat the process of adding the two most recently stored values to find the next Fibonacci number, updating what you store each time.
  5. Keep doing this until you reach the Fibonacci number you need. Since you are storing prior values you're not repeating work.

Code Implementation

def fibonacci_number(n):
    if n <= 1:
        return n

    previous_fib_number = 0
    current_fib_number = 1

    # We iterate to build up to the nth Fibonacci number
    for _ in range(2, n + 1):

        next_fib_number = previous_fib_number + current_fib_number

        # We are storing values, shifting the 'window' forward
        previous_fib_number = current_fib_number

        # This updates current to be the sum just calculated.
        current_fib_number = next_fib_number

    return current_fib_number

Big(O) Analysis

Time Complexity
O(n)The algorithm calculates the nth Fibonacci number iteratively by building up from the base cases (0 and 1). It iterates from 2 up to n, calculating each subsequent Fibonacci number by summing the previous two. The number of iterations is directly proportional to n, the input number. Therefore, the time complexity is O(n), representing linear time complexity with respect to the input n.
Space Complexity
O(1)The algorithm described stores only the two most recently computed Fibonacci numbers. This requires constant extra space, independent of the input number N. No additional data structures that scale with the input are utilized; we just overwrite existing variables. Thus, the auxiliary space complexity is O(1).

Edge Cases

CaseHow to Handle
Input n is zeroReturn 0, as F(0) = 0 is defined as the base case.
Input n is oneReturn 1, as F(1) = 1 is defined as the second base case.
Input n is a large positive integerUse dynamic programming or memoization to avoid stack overflow and potential integer overflow when using recursion.
Negative input nReturn an error or define Fibonacci for negative indices using F(-n) = (-1)^(n+1)F(n).
Integer overflow for large n using iterative solutionUse a larger data type (e.g., long long in C++, BigInteger in Java/Python) or return an error if overflow is unavoidable.
Recursive solution with large n exceeds maximum recursion depthConvert to an iterative (dynamic programming) approach instead of recursion.
Floating-point errors in Binet's formulaAvoid using Binet's formula due to floating-point imprecision; favor dynamic programming or iterative solutions.
Memoization array size for large n exceeds memory limitsConsider a space-optimized dynamic programming approach storing only the last two Fibonacci numbers, rather than an entire array.