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] = 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