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

**Examples:**

Example 1:Input:N = 5Output:0 1 1 2 3 5Explanation:0 1 1 2 3 5 is the fibonacci series up to 5th term.(0 based indexing)Example 2:Input:6Output:0 1 1 2 3 5 8Explanation: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] = 0;
fib[1] = 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] = 0;
fib[1] = 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