Program to find N-th Fibonacci Number in Java

May 18, 2022

N-th Fibonacci Number in Java

 

Here, in this page we will discuss the program to find N-th Fibonacci Number in Java. he sequence F(n) of Fibonacci numbers is defined by the recurrence relation, F(n) = F(n-1) + F(n-2) where, F(0) = 0 and F(1) = 1.

In this page we will discuss the different methods to solve this problem in optimized way.

N-th Fibonacci Number in Java

Method 1 (Using Recursion) :

  • Create a function fib(int n),
  • Inside that function define the base condition, which is if(n<=1) return n,
  • Otherwise return fib(n-1)+fib(n-2).

 

Time and Space Complexity :

  • Time-Complexity : O(n)
  • Space-Complexity : O(1)
N-th Fibonacci number

Code to find N-th Fibonacci Number in Java

Run 
class Main {
  static int fib(int n)
  {   
     if (n <= 1)    //Base Condition
     return n;
     return fib(n - 1) + fib(n - 2);
  }

  public static void main(String args[])
  {
     int n = 4;
     System.out.println(fib(n));
  }
}
Output :

3

Method 2 (Using DP) :

  • Create a function fib(int n),
  • Inside that function, declare an array say f[] to store the fibonacci number.
  • Set, f[0]=0
  • If(n>0):
  • Set, f[1] =1.
  • Now, run a loop from i=2 to i<=n,
  • Set, f[i]=f[i-1]+f[i-2]
  • At last, return f[n].

 

Time and Space Complexity :

  • Time-Complexity : O(n)
  • Space-Complexity : O(n)
N-th Fibonacci

Code in Java

Run 
class Main {
    static int fib(int n)
    {
        int f[] = new int[n + 1];
        int i;
  
        f[0] = 0;
  
        if (n > 0) {
            f[1] = 1;
  
            for (i = 2; i <= n; i++) {
                f[i] = f[i - 1] + f[i - 2];
            }
        }
  
        return f[n];
    }
  
    public static void main(String args[])
    {
        int n = 4;
        System.out.println(fib(n));
    }
}
Output :

3

Method 3 (Using DP with optimized space) :

  • Create a function fib(int n),
  • Inside that function, declare three variables, a=0, b=1 and c.
  • If(n==0), return a.
  • Now run a loop from i=2 to i<=n,
  • Set, c=a+b, a=b and b=c
  • At last, return b.

 

Time and Space Complexity :

  • Time-Complexity : O(n)
  • Space-Complexity : O(1)

Code in Java

Run 
class Main {
  static int fib(int n)
  {
     int a = 0, b = 1, c;
     if (n == 0)
       return a;
     for (int i = 2; i <= n; i++) {
       c = a + b;
       a = b;
       b = c;
     }
     return b;
   }

   public static void main(String args[])
   {
     int n = 4;
     System.out.println(fib(n));
   }
}
Output :

3
While loop in C

2 comments on “Program to find N-th Fibonacci Number in Java”


  • Satendra

    Class fact{
    public static int calf(int n){
    If(n==1|| n==0){
    return 1;
    }
    int n1= calf(n-1);
    Int factorial= n*n1;
    return factorial;
    }
    public static void main (String[]args){
    Int n=5;
    int ans= calf(n);
    system.out.printl(calf);
    }}

    5