Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Recursion & Backtracking

Fibonacci Number

Easy · Recursion & Backtracking · Asked at TCS, Infosys, Wipro, Amazon

The Fibonacci sequence is F(0) = 0, F(1) = 1 and F(n) = F(n-1) + F(n-2). Print F(n).

Input

One integer n.

Output

The value of F(n).

Constraints

Plain recursion is too slow for large n — try a loop or memoization. F(80) needs a 64-bit integer.

Example 1

Input

6

Output

8

Example 2

Input

1

Output

1

Hints

  1. Plain recursion fib(n − 1) + fib(n − 2) recomputes the same values exponentially many times.
  2. Keep only the last two values and loop from 2 to n. F(80) needs a 64-bit integer.

Approach

Each Fibonacci number depends only on the previous two, so iterate with two variables: a = F(i − 1) and b = F(i). Each step does (a, b) = (b, a + b), giving O(n) time instead of O(2^n) for naive recursion. Memoised recursion gives the same O(n). F(80) ≈ 2.3 × 10^16 overflows 32-bit ints.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 0, b = 1;  // F(0), F(1)
    for (int i = 0; i < n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    cout << a << "\n";
    return 0;
}

Python solution

n = int(input())
a, b = 0, 1  # F(0), F(1)
for _ in range(n):
    a, b = b, a + b
print(a)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a = 0, b = 1;  // F(0), F(1)
        for (int i = 0; i < n; i++) {
            long next = a + b;
            a = b;
            b = next;
        }
        System.out.println(a);
    }
}

Solve Fibonacci Number online · All practice problems