Fibonacci Number

Problem Statement

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, typically starting with 0 and 1. Therefore, the sequence begins 0, 1, 1, 2, 3, 5, 8, and so forth. Mathematically, it's defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) for n > 1

Given a non-negative integer n, the task is to compute the n-th Fibonacci number, F(n). The value of n will be within the range from 0 to 30.

Examples

Example 1

Input:

n = 2

Output:

1

Explanation:

F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2

Input:

n = 3

Output:

2

Explanation:

F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3

Input:

n = 4

Output:

3

Explanation:

F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints

• 0 <= n <= 30

Approach and Intuition

Understanding the Problem:

• The Fibonacci sequence is defined recursively. Each term is the sum of the two preceding ones, starting from pre-defined initial terms F(0) = 0 and F(1) = 1.

Examples Analysis:

1. Example 1:

   • Input: n = 2

   • Output: 1

   • Explanation: According to the Fibonacci sequence, F(2) = F(1) + F(0) = 1 + 0 = 1.

2. Example 2:

   • Input: n = 3

   • Output: 2

   • Explanation: Here, F(3) = F(2) + F(1) = 1 + 1 = 2, calculation derived from the results of F(2) and F(1).

3. Example 3:

   • Input: n = 4

   • Output: 3

   • Explanation: In this scenario, F(4) = F(3) + F(2) = 2 + 1 = 3, a result aggregating the results from F(3) and F(2).

Applying Constraints:

• Given the constraints (0 <= n <= 30), the entire range of inputs is small enough to manage computationally without optimizations like memoization or iterative approaches, though using them would indeed make the solution efficient even if the constraints were relaxed.

• Hence, calculating F(n) for the value of n within these bounds can be approached either recursively, iteratively, or using direct mathematical formulas such as Binet's Formula or the matrix exponentiation method to achieve the result more efficiently. Potential implementations could use either of these methods based on requirement and context, ensuring that the frequent repetitive calculations common to naive recursive solutions are minimized or avoided.

Solutions

class Solution {
    public int fibonacci(int n) {
        double phi = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(phi, n) / Math.sqrt(5));
    }
}