Fibonacci Number

tags: result-lookup cache

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

Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints: 0 <= n <= 30

Recursive Implementation

1
2
3
4
5
6
7
8
9

# @param {Integer} n
# @return {Integer}
def fib(n)
  if n == 0 || n == 1
    return n
  end
    
  return fib(n-1) + fib(n-2)
end

Dynamic Programming Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# @param {Integer} n
# @return {Integer}
def fib(n)
  dp = [0,1]

  for i in (2..n)
    dp[i] = dp[i-1] + dp[i-2] 
  end
  
  dp[n]
end

Alternative Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# @param {Integer} n
# @return {Integer}
def fib(n)
  if n == 0 || n == 1
    return n
  end
  
  x = 0
  y = 1
  output = 0

  (n-1).times do
    output = x + y
    x = y
    y = output
  end
  
  output
end

Calculating the Fibonacci sequence can be done using various methods. Here, we’ll discuss two common methods: a simple recursive approach and an iterative approach that uses dynamic programming.

The recursive approach simply follows the definition of the Fibonacci sequence:

1
2
3
4
5
6
7
8

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return self.fib(n - 1) + self.fib(n - 2)

This approach is very simple but highly inefficient for larger values of n, with a time complexity of (O(2^n)).

A more efficient way to calculate Fibonacci numbers is by using dynamic programming and storing previously computed values:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1

        fib_values = [0] * (n + 1)
        fib_values[1] = 1

        for i in range(2, n + 1):
            fib_values[i] = fib_values[i - 1] + fib_values[i - 2]

        return fib_values[n]

This approach uses an iterative method to calculate Fibonacci numbers, storing them in an array. It has a time complexity of (O(n)) and a space complexity of (O(n)).

You can further optimize the space complexity by only keeping track of the last two Fibonacci numbers instead of the whole sequence, reducing the space complexity to (O(1)).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# @param {Integer} n
# @return {Integer}
def fib(n)
  if n == 0 || n == 1
    return n
  end
  
  x = 0
  y = 1
  output = 0

  (n-1).times do
    output = x + y
    x = y
    y = output
  end
  
  output
end

Identifying Problem Isomorphism

“Fibonacci Number” is approximately isomorphic to “Climbing Stairs”.

In “Fibonacci Number”, you have to calculate the ’n’th Fibonacci number. The Fibonacci sequence is one where each number is the sum of the two preceding ones, usually starting with 0 and 1.

In “Climbing Stairs”, you have to find the number of distinct ways you can climb to the top of a staircase that has ’n’ steps, given that you can only take 1 or 2 steps at a time.

The reason behind this mapping is that both problems share a similar underlying structure in terms of calculating the ’n’th term based on the two preceding terms. In “Fibonacci Number”, the ’n’th Fibonacci number is the sum of the (’n-1’)th and the (’n-2’)th Fibonacci numbers. Similarly, in “Climbing Stairs”, the number of ways to reach the ’n’th step is the sum of the ways to reach the (’n-1’)th step and the (’n-2’)th step.

“Fibonacci Number” is simpler than “Climbing Stairs”, because the Fibonacci sequence has no constraints. “Climbing Stairs” involves a specific problem context, i.e., climbing steps one or two at a time. “Fibonacci Number” is simpler than “Climbing Stairs”.

1
2
3
4
5
6
7

class Solution:
    def fib(self, N: int) -> int:
    	a, b = 0, 1
    	for i in range(N): 
				a, b = b, a + b

    	return a

Problem Classification

The given problem statement falls under the domain of Mathematics and specifically, Number Sequences.

The “What” components are as follows:

  1. Fibonacci sequence: The problem is based on the concept of the Fibonacci sequence, which is a mathematical series where each number is the sum of the two preceding ones.

  2. Input: The problem requires an integer input, n.

  3. Output: The output is the nth number in the Fibonacci sequence.

The problem can be further classified as a Recursive Problem. This is because the Fibonacci sequence is inherently recursive - each number in the sequence (after the first two) is calculated by summing the two immediately preceding numbers.

The problem could also fall under the category of Dynamic Programming if the solution involves storing previously calculated values to avoid redundant calculations. However, this would only be apparent after considering the solution strategy.

Language Agnostic Coding Drills

  1. Dissecting the Code:

The code uses several coding concepts:

  • Variable Initialization: a, b = 0, 1
  • Loop: for i in range(N)
  • Multiple Variable Assignment in one line: a, b = b, a + b
  • Returning Value from Function: return a

  1. Ordered List of Concepts:

    • Variable Initialization (Easy): This is the process of assigning a starting (initial) value to a variable. In this case, a and b are both initialized to the first two numbers in the Fibonacci sequence, 0 and 1.

    • Loop (Easy to Medium): Loops are used to repeat a certain block of code. In this case, a ‘for’ loop is used to iterate N times. The difficulty level depends on the learner’s previous experience with loops.

    • Multiple Variable Assignment (Medium): This is a process of assigning values to multiple variables in a single line. It can be a bit confusing for beginners because it requires an understanding of how Python handles simultaneous assignments. In this case, the values of a and b are updated in each iteration in a way that represents the Fibonacci sequence.

    • Returning Value from Function (Easy): After the loop finishes executing, the function returns the final value of a, which is the Nth number in the Fibonacci sequence.

  2. Problem-Solving Approach:

    • The solution starts by initializing two variables, a and b, to the first two numbers in the Fibonacci sequence.

    • It then enters a loop that iterates N times.

    • Inside the loop, it performs the crucial step of updating a and b in each iteration to represent the Fibonacci sequence. Specifically, it updates a to the current value of b and updates b to the sum of its current value and the current value of a. Because these updates need to occur simultaneously, it uses a single line of code to perform both assignments.

    • Finally, after the loop finishes executing, the solution returns the final value of a, which represents the Nth number in the Fibonacci sequence.

This approach effectively calculates the Nth number in the Fibonacci sequence in a way that is efficient and straightforward, and it can be easily adapted to work with any Fibonacci-like sequence by changing the initial values of a and b and the way they’re updated inside the loop.

Targeted Drills in Python

  1. Python-based Coding Drills:

    • Variable Initialization: This concept is fundamental to programming in any language. It’s the act of assigning a value to a variable. In Python, we simply use the “=” operator to do this.

      1
2
3

      x = 10
y = 'Hello World'
print(x, y)  # Output: 10 Hello World

    • Loop: Loops are used to repeat blocks of code. The ‘for’ loop in Python is often used to repeat code a specific number of times.

      1
2
3

      for i in range(5):
    print(i)
# Output: 0 1 2 3 4

    • Multiple Variable Assignment: Python allows for multiple assignments in a single line. This can be a useful shorthand in certain situations.

      1
2

      a, b = 0, 1
print(a, b)  # Output: 0 1

    • Returning Value from Function: A function in Python uses the return keyword to send back a result. If no return statement is hit during the execution of the function, it will implicitly return None.

      1
2
3

      def add(x, y):
    return x + y
print(add(3, 2))  # Output: 5

  2. Problem-Specific Concepts:

    The main problem-specific concept in this task is understanding the Fibonacci sequence. The Fibonacci sequence is a series of numbers where a number is the sum of the two preceding ones, usually starting with 0 and 1. This is essential for our problem because the solution relies on this sequence.

  3. Integration of Concepts:

    The drills can be assembled to solve the problem in the following way:

    • Start by initializing two variables a and b to 0 and 1 respectively.

    • Begin a loop that will iterate n times.

    • In each iteration of the loop, reassign the values of a and b such that a takes the value of b and b takes the value of a + b. This simulates moving two steps down the Fibonacci sequence.

    • After the loop finishes running, the value of a should be the nth number in the Fibonacci sequence. Return a.