Fibonacci numbers grow past the safe range of number quickly. Compute them exactly with bigint, remembering every value already worked out.
What to build
A program that answers Fibonacci queries with a shared cache and reports how many new values each query computed.
Requirements
- Write
fib(n: number): bigintwith F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2), caching results in aMap<number, bigint>shared by all queries. - For each query n, print
fib(N) = VALUE (new: K), where K is how many values were computed and stored during that query.
Input
Line 1: q. Then q lines, each a whole number n.
Output
q lines.
Constraints
1 ≤ q ≤ 20; 0 ≤ n ≤ 300.
Example
Input:
3
10
5
12
Output:
fib(10) = 55 (new: 11)
fib(5) = 5 (new: 0)
fib(12) = 144 (new: 2)
Why it works
bigint keeps every digit, while a number loses precision after F(78); the cache turns an exponential recursion into one computation per value, and counting misses shows that later queries reuse earlier work.
Examples
Example 1 · Input
3 10 5 12
Expected output
fib(10) = 55 (new: 11) fib(5) = 5 (new: 0) fib(12) = 144 (new: 2)
Example 2 · Input
2 0 1
Expected output
fib(0) = 0 (new: 1) fib(1) = 1 (new: 1)
Hints
Hint 1
Keep a Map<number, bigint> as the cache, and count how often a value is not found in it.
Hint 2
String(value) prints a bigint without the trailing n that console.log adds.
Solution
Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";
const cache = new Map<number, bigint>();
let computed = 0;
function fib(n: number): bigint {
const known = cache.get(n);
if (known !== undefined) return known;
const value = n < 2 ? BigInt(n) : fib(n - 1) + fib(n - 2);
cache.set(n, value);
computed++;
return value;
}
const q = Number(read());
for (let i = 0; i < q; i++) {
const n = Number(read());
const before = computed;
const value = fib(n);
console.log("fib(" + n + ") = " + String(value) + " (new: " + (computed - before) + ")");
}