# Print Fibonacci Series up to Nth term

Problem Statement: Given an integer N. Print the Fibonacci series up to the Nth term.

Examples:

```Example 1:
Input: N = 5
Output: 0 1 1 2 3 5
Explanation: 0 1 1 2 3 5 is the fibonacci series up to 5th term.(0 based indexing)

Example 2:
Input: 6

Output: 0 1 1 2 3 5 8
Explanation: 0 1 1 2 3 5 8 is the fibonacci series upto 6th term.(o based indexing)```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Naive approach

Intuition: As we know fib(i) = fib(i-1) + fib(i-2).Simply iterate and go on calculating the ith term in the series.

Approach:

• Take an array say fib of size n+1.The 0th term and 1st term are 0 and 1 respectively.So fib(0)=0 and fib(1)=1.
• Now iterate from 2 to n and calculate fib(n).fib(n)=fib(n-1) + fib(n-2).
• Then print fib(0) + fib(1) + …………fib(n).

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

int main() {
int n = 5;
if (n == 0) {
cout << 0;
} else if (n == 1) {
cout << 0 << " " << 1 << "\n";
} else {
int fib[n + 1];
fib = 0;
fib = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
cout<<"The Fibonacci Series up to "<<n<<"th term:"<<endl;
for (int i = 0; i <= n; i++) {
cout << fib[i] << " ";
}
}
}
``````

Output:

The Fibonacci Series up to 5th term:
0 1 1 2 3 5

Time Complexity: O(n)+O(n), for calculating and printing the Fibonacci series.

Space Complexity: O(n), for storing Fibonacci series.

## Java Code

``````public class TUF {
public static void main(String args[]) {
int n = 5;
if (n == 0) {
System.out.println(0);
} else {
int fib[] = new int[n + 1];
fib = 0;
fib = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
System.out.println("The Fibonacci Series up to "+n+"th term:");
for (int i = 0; i <= n; i++) {
System.out.print(fib[i] + " ");
}
}
}
}
``````

Output:

The Fibonacci Series up to 5th term:
0 1 1 2 3 5

Time Complexity: O(n)+O(n), for calculating and printing the Fibonacci series.

Space Complexity: O(n), for storing Fibonacci series.

Solution 2: Space optimized

Intuition: For calculating the ith term we only need the last and second last term i.e (i-1)th and (i-2)th term, so we don’t need to maintain the whole array.

Approach:

• Take two variables last and secondLast for storing (i-1)th and (i-2)th term.
• Now iterate from 2 to n and calculate ith term. ith term is last + secondLast term.
• Then update secondLast term to last term and last term to ith term as we iterate.

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 5;
if (n == 0) {
cout<<"The Fibonacci Series up to "<<n<<"th term:"<<endl;
cout << 0;
}
else {
int secondLast = 0;//for (i-2)th term
int last = 1;//for (i-1)th term
cout<<"The Fibonacci Series up to "<<n<<"th term:"<<endl;
cout << secondLast << " " << last << " ";
int cur; //for ith term
for (int i = 2; i <= n; i++) {
cur = last + secondLast;
secondLast = last;
last = cur;
cout << cur << " ";
}
}
}
``````

The Fibonacci Series up to 5th term:
0 1 1 2 3 5

Time Complexity: O(N).As we are iterating over just one for a loop.

Space Complexity: O(1).

## Java Code

``````public class TUF {
public static void main(String args[]) {
int n = 5;
if (n == 0) {
System.out.println("The Fibonacci Series up to "+n+"th term:");
System.out.print(0);
} else {
int secondLast = 0;
int last = 1;
System.out.println("The Fibonacci Series up to "+n+"th term:");
System.out.print(secondLast + " " + last + " ");
int cur;
for (int i = 2; i <= n; i++) {
cur = last + secondLast;
secondLast = last;
last = cur;
System.out.print(cur + " ");
}
}
}
}
``````

The Fibonacci Series up to 5th term:
0 1 1 2 3 5

Time Complexity: O(N).As we are iterating over just one for a loop.

Space Complexity: O(1).

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article