LeetCode #509 Fibonacci Number Solution & Explanation

Fibonacci numbers, also known as the magic numbers, have made significant contributions across various fields.

LeetCode Problem

LeetCode #509 Problem
LeetCode #509 Examples
LeetCode #509 Constraints

Solution

Actually, this is not the first time we have faced this problem.

We can see similar question :

And we can just finish this problem with almost the same way haha!

C# Solution

Solution1 – using three variables

public class Solution {
    public int Fib(int n) {
        int first  = 0;     
        int second = 1;     
        int tmp = 0;        
        
        if(n<2)   
        {
            return n;
        }
        else
        {
            for(int i =2; i<=n;i++) 
            {
                tmp = second;       
                second+=first;     
                first = tmp;        
            }
        }
        return second;
    }
}

Runtime : 25ms、24ms、28ms (faster than 40~70%)

Solution2 – using one array

public class Solution {
    public int Fib(int n) {
        int[] arr = new int[31];
        arr[0] = 0;
        arr[1] = 1;
        
        for(int i = 2; i<=n; i++)
        {
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
}

We can the array size as 31 is because (Constraints : 0<=n<=30)

The maximum of n is 30, and because index start from zero, so it needs to plus one.

Runtime : 23ms、24ms、23ms (faster than 70~80%)

⭐ If the range of n is larger, it is recommended to dynamically set the array length.

➡ This can help avoid excessive memory usage.

Java Solution

Solution1 – using one array

class Solution {
    public int fib(int n) {
        int[]arr = new int[31];

        arr[0] = 0;
        arr[1] = 1;
        
        for(int i = 2; i<=n; i++)
        {
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
}

Runtime : 0ms、0ms、0ms

Python3 Solution

Solution1 – using list

class Solution:
    def fib(self, n: int) -> int:
        arr = [0,1]
        
        for i in range(2,n+1):
            arr.append(arr[i-1]+arr[i-2])
        
        return arr[n]

JavaScript Solution

Solution1

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    arr = [0,1];
    
    for(let i = 2; i<=n; i++)
    {
        arr[i] = arr[i-1]+arr[i-2];
        //arr.push(arr[i-1]+arr[i-2])  //you can choose which one to use
    }
    return arr[n];
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad or sharing my posts, Thanks a lot

If you got any problem about the explanation, please feel free to let me know

The problem link : Fibonacci Number – LeetCode

Random post

Leave a Reply

Your email address will not be published. Required fields are marked *