Fibonacci

• LintCode: No.366-Fibonacci
• Problem:

  Find the Nth number in Fibonacci sequence.
  A Fibonacci sequence is defined as follow:
    * The first two numbers are 0 and 1.  
    * The i th number is the sum of i-1 th number and i-2 th number.
    * The first ten numbers in Fibonacci sequence is:
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
  

• Note:

  The Nth fibonacci number won't exceed the max value of signed 32-bit integer in the test cases.

• Analysis:

  According to problem statement, the formula is as following:

    Fib(n) = Fib(n-1) + Fib(n-2), n >= 3  
    Fib(1) = 0, Fib(2) = 1
  

• Java:

  • Iterative

      public class Solution { 
          public int fibonacci(int n) {
              if (n == 1 || n <= 0) {
                  return 0;
              }
              if (n == 2) {
                  return 1;
              }
              int a = 0; // fib(1)
              int b = 1; // fib(2)
              int sum = 0; // fin(n)
              for (int i = 3; i <= n; i++) {
                  sum = a + b;
                  a = b;
                  b = sum;
              }
              return sum;
          }
      }
    

  • Recursive

      public class Solution {
          public int fibonacci(int n) {
              if (n == 1|| n <= 0) {
                  return 0;
              }
              if (n == 2) {
                  return 1;
              }
              return fibonacci(n - 1) + fibonacci(n - 2);
          }
      }
    

• Time Complexity:
  • Iterative: O(n)
  • Recursive: O(2^n)