> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/501-600/fibonacci-number.md).

# 509. Fibonacci Number

### Description

The **Fibonacci numbers**, commonly denoted `F(n)` form a sequence, called the **Fibonacci sequence**, such that each number is the sum of the two preceding ones, starting from `0` and `1`. That is,

F(0) = 0

F(1) = 1

F(n) = F(n - 1) + F(n - 2), for n > 1.

Given `n`, calculate `F(n)`.

### Constraints

* `0 <= n <= 30`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/fibonacci-number/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** n = 2

**Output:** 1

**Explanation:** F(2) = F(1) + F(0) = 1 + 0 = 1.
{% endtab %}

{% tab title="Example 2" %}
**Input:** n = 3

**Output:** 2

**Explanation:** F(3) = F(2) + F(1) = 1 + 1 = 2.
{% endtab %}

{% tab title="Example 3" %}
**Input:** n = 4

**Output:** 3

**Explanation:** F(4) = F(3) + F(2) = 2 + 1 = 3.
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(2^N), The amount of operations needed, for each level
 *     of recursion, grows exponentially as the depth approaches N.
 * Space complexity : O(N), We need space proportionate to N to account for 
 *    the max size of the stack, in memory.
 */

public class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }
        return fib(N-1) + fib(N-2);
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public int fib(int n) {
        if(n < 2) {
            return n;
        }
        int prev = 0;
        int curr = 1;
        for(int i = 2; i <= n; i++) {
            int temp = prev + curr;
            prev = curr;
            curr = temp;
        }
        return curr;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*