Medium · sliding pair

Fibonacci Number

F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2). Compute it with a sliding pair — then compare with the exponential recursion from Lesson 5.

Problem

Input: one integer n (0 ≤ n ≤ 45).

Output: F(n), where F(0) = 0 and F(1) = 1. (F(45) = 1,134,903,170 — the largest that fits in an int.)

Sample:

Input	Output
`10`	`55`
`20`	`6765`

Program.cs — your solution

Custom input for "Run my input"

Judging runs entirely in your browser against hidden tests. Your code is saved locally as you type. Ctrl+Enter judges.

Hint 1 — the sliding pair

Keep two variables a = 0, b = 1. Each pass: int t = a + b; a = b; b = t;. After n passes, a is F(n).

Hint 2 — why not the recursion from Lesson 5?

Fib(45) recursively makes ~2 billion calls. The sliding pair makes 45. Same math, exponentially different cost — that's algorithmic thinking.

Solution (try first!)

int n = int.Parse(Console.ReadLine());
int a = 0, b = 1;
for (int i = 0; i < n; i++) { int t = a + b; a = b; b = t; }
Console.WriteLine(a);

You've reached the top of the problem set — revisit the list, or read Lesson 5 on when recursion IS the right tool.