The Fibonacci Sequence is the series of numbers:

Your goal is to write an**optimal** method - **O(n)** and use constant **O(1)** space. With this implementation, your method should be able to compute larger sequences where n > 40.

**Examples**:

`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...`

The next number is found by adding up the two numbers before it.Your goal is to write an

`betterFibonacci`

that returns the `nth`

Fibonacci number in the sequence. `n`

is 0 indexed, which means that in the sequence `0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...`

, n == 0 should return 0 and n == 3 should return 2. Your method should exhibit a runtime complexity of `fib(0) ==> 0`

`fib(1) ==> 1`

`fib(3) ==> 2`

Need a **hand?** Try out these hints, one at a time.

You may have solved this problem before with the naive recursive algorithm - **O(1)**.

`fib(n) = fib(n-1) + fib(n-2)`

. The thing to note is that at every stack level, this algorithm only needs the previous 2 numbers to compute the current number in the series. Armed with this information, let's replace the recursive calls with variables that hold this information! Since we will be using only 2 variables at any time, the space complexity will be
1) Use 2 variables -

2) Create a variable to hold intermediate values :

3) Check for base conditions and break early :

4) Run a loop from 2 to

`int n_2 = 0`

and `int n_1 = 1`

to represent `fib(n-2)`

and `fib(n-1)`

in the recursive implementation.2) Create a variable to hold intermediate values :

`int temp`

3) Check for base conditions and break early :

if(n == 0) return n_2;

else if(n == 1) return n_1;

4) Run a loop from 2 to

`n`

, and keep on switching the variables as per the fibonacci sequence. Finally, return `n_1`

: for(int i = 2; i <= n; i++){

temp = n_1 + n_2;

n_2 = n_1;

n_1 = temp;

}

return n_1;

public static int betterFibonacci(int n) { }

**C**

**Java**

**Python**