Leetcode: Interview question 10-I. Fibonacci sequence

The topic

Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:

F (0) = 0, F (1) = 1, F (N) = F (N - 1) + F (N - 2), where N > 1.Copy the code

The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers. 1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Example 1:

Input: n = 2 Output: 1Copy the code

Example 2:

Input: n = 5 Output: 5Copy the code

Tip:

0 <= n <= 100
Copy the code

Solution 1: Recursion

F (n) = f(n-1) + f(n-2) It’s silly to write recursively, it does a lot of unnecessary repetitions, it takes too long, so I won’t show you.

Solution 2: Iterates over arrays

Using the rule that the third number is the sum of the first two numbers, use an array ARR to store the Fibonacci sequence starting from 0 in a loop.

var fib = function(n) {
  if (n < 2) return n

  let arr = [0, 1]

  for (let i = 2; i <= n; i++) {
    arr[i] = (arr[i-1] + arr[i-2]) % 1000000007
  }

  return arr[arr.length-1]
};
Copy the code

Time complexity: O(n) Space complexity: O(n)

Solution 3: Iterative movement

Using the rule that the third number is the sum of the first two numbers, the two variables A1, A2 move bit by bit to the right in the loop.

var fib = function(n) {
  if (n < 2) return n

  let a1 = 0
  let a2 = 1
  let tmp = 0

  for (let i = 2; i <= n; i++) {
    tmp = a2
    a2 = (a1 + a2) % 1000000007
    a1 = tmp
  }

  return a2
};
Copy the code

Time complexity: O(n) Space complexity: O(1)

Solution 4: Mathematical general term formula

From a mathematical point of view, directly use the Fibonacci sequence to the formula:

var fib = function(n) {
  if (n < 2) return n

  const sqrt5 = Math.sqrt(5)
  return ((Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n)) / sqrt5) % 1000000007
};
Copy the code

Time complexity: O(logn) Space complexity: O(1)