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,
and for n > 1,
Problem
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)”