# 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,

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)