Read N and print the Nth Fibonacci number. F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2).
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... — each number is the sum of the previous two.
Three canonical approaches, in increasing sophistication:
Recursion (bad — O(2^N)) demonstrates the definition literally.
Iteration (good — O(N) time, O(1) memory) is the pragmatic solution.
Matrix exponentiation (O(log N)) is what you use if N is really big.
0
0
10
55
50
12586269025
Runnable starter code. Click "Try in playground" to open pre-loaded with the test fixtures.
n = int(input())
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
print(a)
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
long a = 0, b = 1;
for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
System.out.println(a);
}
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
long long a = 0, b = 1;
for (int i = 0; i < n; ++i) { long long t = a + b; a = b; b = t; }
cout << a << "\n";
}