13. Nth Fibonacci Number

The problem can be found at the following link: Question Link

My Approach

I use an iterative approach to calculate the nth Fibonacci number. I maintain two variables, secondLast and last, to keep track of the last two Fibonacci numbers. I iterate n-1 times to calculate the nth Fibonacci number.

• Initialize the 1st Fibonacci number to 0 using the variable secondLast, and the 2nd Fibonacci number to 1 using last variable.

• Proceed with a loop for the remaining n-1 iterations, updating curr as the sum of secondLast and last. Subsequently, shift the value of last to secondLast, and assign the value of curr to last for the upcoming iterations.

Explanation with Example

Let's take an example where n is 5.

-  Iteration 1: secondLast = 0  ,  last = 1  ,  curr = (0 + 1) = 1
-  Iteration 2: secondLast = 1  ,  last = 1  ,  curr = (1 + 1) = 2
-  Iteration 3: secondLast = 1  ,  last = 2  ,  curr = (1 + 2) = 3
-  Iteration 4: secondLast = 2  ,  last = 3  ,  curr = (2 + 3) = 5

So, the 5th Fibonacci number is 5.

Time and Auxiliary Space Complexity

• Time Complexity: The loop runs for n-1 iterations, resulting in a linear time complexity of O(n).

• Auxiliary Space Complexity: The algorithm uses a constant amount of extra space, resulting in an auxiliary space complexity of O(1).

Code (C++)

class Solution {
  public:
    int MOD = 1e9+7;
    int nthFibonacci(int n){
        int secondLast = 0;
        int last = 1;
        int curr = 1;
        
        n = n-1;
        while(n--){
            curr = (last + secondLast)%MOD;
            secondLast = last;
            last = curr;
        }
        
        return curr;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.