data-structures · beginner · ~15 min

Fibonacci (bottom-up)

Compute Fibonacci in O(n) with a rolling pair, not exponential recursion.

Challenge

Implement:

long long fib(int n);

Return the n-th Fibonacci number (fib(0)=0, fib(1)=1). Build the answer bottom-up. 0 <= n <= 90.

Input format

n in [0,90].

Output format

The n-th Fibonacci number.

Constraints

Use long long; fib(90) overflows 32 bits.

Starter code

#include <stddef.h>
/* Return the n-th Fibonacci number (fib(0)=0, fib(1)=1). 0<=n<=90. */
long long fib(int n){ (void)n; return 0; }

Common mistakes

Naive recursion is exponential; recompute nothing — keep two rolling values.

Edge cases to handle

fib(0)=0, fib(1)=1.

Background lessons

Solve this exercise in the browser editor — compile and run against the test harness, no setup required.