Fibonacci Number

Problem

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

Solution

The problem Fibonacci Number can be solved using 2 variables to hold current and previous fibonacci numbers.

Implementation

class Solution
{
  public:
    int fib(int n)
    {
        int fib[2] = {0, 1};
        for (int i = 2; i <= n; i++)
            fib[i & 1] += fib[(i + 1) & 1];

        return fib[n & 1];
    }
};