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