Fibonacci Numbers Solution (O(1) auxiliary space)

In mathematics, the Fibonacci series (Fn) is a sequence, such that each number in the series is the sum of the two preceding ones, starting from 0 and 1. That is,

{\displaystyle F_{0}=0,\quad F_{1}=1,}

and for n > 1,

{\displaystyle F_{n}=F_{n-1}+F_{n-2}}

Problem Statement

Input a number n, print n-th Fibonacci Number. 

Examples: 

Input  : n = 2
Output : 1

Input  : n = 10
Output : 34

This problem could be solved by Dynamic Programming

Optimal Substructure
F[i] is the ith Fibonacci number
And, 
 F[0] = 0, F[1] = 1
Thus for n > 1, 
 F[i] = F[i-1] + F[i-2];

Fibonacci Numbers Solution

Code Implementation
//
//  main.cpp
//  Fibonacci numbers
//
//  Created by Himanshu on 22/09/21.
//

#include <iostream>
using namespace std;

int solve (int n) {
    int F[n+1];
    
    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    }
    
    for (int i=0; i<=n; i++) {
        F[i] = 0;
    }
    
    F[1] = 0;
    F[2] = 1;

    for (int i=3; i<=n; i++) {
        F[i] = F[i-1] + F[i-2];
    }

    return F [n];
}

int main() {
    int n = 15;
    
    printf("%dth Fibonacci number is %d\n", n, solve(n));
    return 0;
}

Output

15th Fibonacci number is 377

Time Complexity: O(n)
Auxiliary Space: O(n)

Fibonacci numbers with O(1) Auxiliary space

To find the nth fibonacci number, we need not store previous Fibonacci numbers in an array. We could use two temporary variables instead of an array to store previous fibonacci numbers n-1 and n-2 and keep updating them with each iteration.

Thus we could find nth fibonacci number in O(1) auxiliary space.

Code Implementation
//
//  main.cpp
//  Fibonacci numbers
//
//  Created by Himanshu on 22/09/21.
//

#include <iostream>
using namespace std;

int solve (int n) {
    
    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    }
    
    int n1 = 0, n2 = 1, fn = 0;
    
    for (int i=3; i<=n; i++) {
        fn = n1 + n2;
        n1 = n2;
        n2 = fn;
    }

    return fn;
}

int main() {
    int n = 15;
    
    printf("%dth Fibonacci number is %d\n", n, solve(n));
    return 0;
}

Output

15th Fibonacci number is 377

Time Complexity: O(n)
Auxiliary Space: O(1)

One thought on “Fibonacci Numbers Solution (O(1) auxiliary space)

Leave a Reply

Your email address will not be published.