Compute the Nth Fibonacci Numbers using Iterative and Math Algorithms

The Fibonacci sequence goes like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, … The next number can be found by adding up the two numbers before it, and the first two numbers are always 1. Write a function that takes an integer n and returns the nth Fibonacci number in the sequence.

Note: n will be less than or equal to 30.

Example 1
Input
n = 1
Output
1
Explanation
This is the base case and the first fibonacci number is defined as 1.

Example 2
Input
n = 6
Output
8
Explanation
Since 8 is the 6th fibonacci number: 1, 1, 2, 3, 5, 8.

Example 3
Input
n = 7
Output
13
Explanation
Since 13 is the seventh number: 1, 1, 2, 3, 5, 8, 13

Iterative Algorithm to Compute the Nth Fibonacci Number

Iteratively, we can compute the next item in the Fibonacci sequences.

1
2
3
4
5
6
7
8
9
10

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

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

The complexity is O(N) as we are iterating N times to find the Nth Fibonacci number. The space complexity is O(1) constant.

Using Binet’s Formula to Compute the Nth Fibonacci Number

According to Binet’s Formula, we can compute the Nth Fibonacci Number by the followign equation:

Thus, the following C++ computes the Nth Fibonacci Number using this equation which runs O(1) time and O(1) space (assuming the equation computation is O(1) constant))

1
2
3

int solve(int n) {
   return (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (pow(2, n) * sqrt(5));
}

int solve(int n) {
   return (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (pow(2, n) * sqrt(5));
}

–EOF (The Ultimate Computing & Technology Blog) —