Find Nth Fibonacci Number

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

Write a function int fib(int n) that returns . For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return 

Solution1: dp

Avoid the repeated calculating. Time Complexity: O(n). Extra Space: O(n).

public class FindNthFibonacciNumber {
    public static void main(String[] args) {
        int n = 9;
        System.out.println(fib(n));
    }
 
    public static int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
  
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
  
        return dp[n];
    }
  
}

Solution2: Space Optimized 

Storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.
Time Complexity: O(n). Extra Space: O(1).

//space optimized
 public static int fib(int n) {
     int a = 0;
     int b = 1;
  
     if(n == 0) {
        return a;
     }
  
     for(int i = 2; i <= n; i++) {
         int c = a + b;
         a = b;
         b = c;
     }
     return b;
 }

Reference: http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ 

Follow Up: How to check whether n is Fibonacci number
Solution: A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square

//A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square
 public static boolean checkFib(int n) {
     return isPerfectSquare(5*n*n + 4) || isPerfectSquare(5*n*n - 4);
 }
 
 public static boolean isPerfectSquare(int x) {
     int s = (int) Math.sqrt(x);
     if(s * s == x) {
         return true;
     }else {
         return false;
     }
 }