Fibonacci Number – Leetcode #509

Problem Statement

This problem is from Leetcode – Fibonacci numbers. The problem statement in short is given below:

Compute the nth Fibonacci number where

F(0) = 0,

F(1) = 1, and

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

Solution:

This problem is simple enough. Lets take the iterative approach first. See the code sample below:

public int fib(int n) {

		int fib = 0;
		
		// declare the initial variables as 0, 1
		int prev = 0;
		int cur = 1;

		for(int i=0; i<n; i++) {
			
			// fib is addition of previous two numbers
			fib = prev + cur;
			
			// update previous two numbers
			prev = cur;
			cur = fib;

		}

		return prev;

	}

You can checkout the code from Github here: Fibonacci Number – First Approach. See the performance of this approach below:

PERFORMANCE ANALYSIS

RUNTIME	0 ms | Beats 100.00 %
MEMORY	39.70 MB | Beats 99.87 %
TIME COMPLEXITY	O (N)