1.

Write a program in Java to generate the Nth Fibonacci Number using Iteration and Constant Space.

Answer»

Fibonacci Series is a series in which the Nth term is the sum of the previous 2 terms i.e. (N-1)th and (N-2)th terms. The first 2 terms of the Fibonacci sequence are always known. They are 0 and 1 respectively. After this, the further terms can be generated as follows:

So, in general, we can derive a generic term i.e.

Fib(N) = Fib(N - 1) + Fib(N - 2)

So, let us now write a program to find the Nth Fibonacci Number using iteration.

a. Java Program to generate Nth Fibonacci Number using Iteration.

import java.util.*;
class Main {
public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();

int a = 0; //0th fibonacci number
int b = 1; //1st fibonacci number

if(n < 0) {
System.out.println("N cannot be negative");
return;
}

if(n == 0) System.out.println(a);
else if(n == 1) System.out.println(b);
else {
int c = 0;
for(int i=2;i<=n;i++) {
c = a + b;
a = b;
b = c;
}

System.out.println(c);
}

}
}

Sample Input/Output: Run Code

Input: 7
Output: 13


  • Corner Cases You might Miss: The simple mistake of not handling the corner case when N is negative can happen to a lot of programmers. Since the number of terms can’t be negative, this should be handled separately as shown in the code above.


  • Time Complexity: O(N) because we have to travel N terms


  • Auxiliary Space:  O(1) as no extra space is used.


  • Follow up: You can also solve this problem using dynamic programming. This will take up O(N) space as well and the time complexity will be the same i.e. O(N). Try the dynamic programming approach yourself.


Discussion

No Comment Found

Related InterviewSolutions