These are the notes for JavaScript Coding Questions, episode 3, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three classic number questions: the GCD and LCM of two numbers, the factorial of a big number, and the n-th Fibonacci number. The obvious attempts fail in three new ways: too slow (a loop of almost a billion steps), not exact (JavaScript numbers quietly round after 2⁵³) and a crashed call stack (RangeError: Maximum call stack size exceeded).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Plain modern JavaScript, no packages.
About the timings. Lines like
big: 1.518sare copied from a real run on one machine. Times vary from machine to machine and from run to run; what matters is the size of the gap (seconds vs milliseconds), not the exact number.
Q1: GCD and LCM
Problem. Write gcd(a, b) and lcm(a, b) for whole numbers a, b ≥ 0.
- The GCD (greatest common divisor, also called HCF, highest common factor) is the biggest number that divides both a and b with remainder 0.
gcd(48, 18) = 6. - The LCM (least common multiple) is the smallest positive number that both a and b divide.
lcm(4, 6) = 12. - Two numbers whose GCD is 1 are called coprime:
gcd(7, 13) = 1.
Real life. Simplifying a fraction: 18/48 = 3/8 because gcd(18, 48) = 6. Two buses leave the stand together, one every 4 minutes and one every 6 minutes: they leave together again after lcm(4, 6) = 12 minutes.
Think out loud
- Input: two whole numbers. Output: one whole number.
- Edge cases: one of them is 0 (
gcd(0, 5)is 5, because every number divides 0), two big primes (GCD 1, the worst case for a search), and an LCM whose producta * bis huge.
The obvious attempt: count down
function gcd(a, b) {
for (let d = Math.min(a, b); d >= 1; d--) {
if (a % d === 0 && b % d === 0) return d;
}
}
console.log(gcd(48, 18), gcd(7, 13), gcd(0, 5));
console.time("big");
console.log(gcd(1000000007, 998244353));
console.timeEnd("big");
Output:
6 1 undefined
1
big: 1.518s
Why it fails.
gcd(0, 5): the smaller number is 0, sodstarts at 0, the conditiond >= 1is false straight away, the loop never runs, and the function falls off the end. A function that ends withoutreturngivesundefined.- Two big primes share only the divisor 1, so the loop counts down from 998244353 almost to 1: about a billion steps. O(min(a, b)) time.
Euclid's algorithm
Real-life picture: tiling a floor. A floor is 48 × 18. You want the biggest square tile that covers it exactly. Lay the biggest squares you can (18 × 18): two fit, and a 12 × 18 strip is left (48 % 18 = 12). On the strip, 12 × 12 squares leave 6 × 12 (18 % 12 = 6). Then 6 × 6 squares leave nothing (12 % 6 = 0). So the answer is 6.
Any tile that fits the whole floor also fits every leftover strip, and the other way round, so the answer never changes from one step to the next:
gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
console.log(gcd(48, 18), gcd(7, 13), gcd(0, 5), gcd(5, 0));
console.time("big");
console.log(gcd(1000000007, 998244353));
console.timeEnd("big");
Output:
6 1 5 5
1
big: 0.034ms
[a, b] = [b, a % b] is array destructuring: the right side builds the array [b, a % b] from the old values first, then both are assigned together, so no temporary variable is needed.
The recursive form is just as common in interviews (the depth is tiny, so no stack worries):
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
console.log(gcd(48, 18), gcd(1071, 462), gcd(0, 0));
6 21 0
(gcd(0, 0) is defined as 0 by convention.)
Why it's fast. After two steps the bigger number has at least halved (if b ≤ a/2 then a % b < b ≤ a/2; if b > a/2 then a % b = a - b < a/2). So for numbers near a billion, Euclid needs at most about 60 steps. Time O(log min(a, b)), space O(1).
LCM: the obvious attempt
The rule: gcd(a, b) × lcm(a, b) = a × b. So lcm = a * b / gcd.
function gcd(a, b) {
while (b !== 0) [a, b] = [b, a % b];
return a;
}
const lcm = (a, b) => a * b / gcd(a, b);
console.log(lcm(4, 6), lcm(21, 6));
console.log(lcm(123456789, 246913578));
Output:
12 42
246913577.99999997
Why. 123456789 * 246913578 is about 3.05 × 10¹⁶, more than Number.MAX_SAFE_INTEGER (about 9 × 10¹⁵). Past that limit a Number can't store every whole number, so the product is rounded, and dividing the rounded product can no longer come out whole. An LCM with a decimal point is impossible.
LCM: the fix, divide first
a / gcd(a, b) is always a whole number (the GCD divides a) and smaller than a, so dividing first keeps every step small:
function gcd(a, b) {
while (b !== 0) [a, b] = [b, a % b];
return a;
}
function lcm(a, b) {
if (a === 0 || b === 0) return 0;
return a / gcd(a, b) * b;
}
console.log(lcm(4, 6), lcm(21, 6), lcm(0, 5));
console.log(lcm(123456789, 246913578));
Output:
12 42 0
246913578
The LCM with a zero is 0 by convention (and without the check, 0 / gcd(0, 0) would be 0 / 0, which is NaN).
If the LCM itself is bigger than 2⁵³, even "divide first" can't be exact in a Number: use BigInt (Q2). For example, lcm(123456789, 987654321) is 13548070123626141, but the Number version prints 13548070123626140; BigInt(123456789) * 987654321n / 9n gives 13548070123626141n.
Complexity
| Time | Extra space | |
|---|---|---|
| Count down from min(a, b) | O(min(a, b)) | O(1) |
| Euclid | O(log min(a, b)) | O(1) |
| LCM via Euclid | O(log min(a, b)) | O(1) |
Q2: Factorial of n
Problem. Return n! = 1 × 2 × 3 × ... × n, with 0! = 1. Make it exact for big n like 25 or 100.
Real life. n! is the number of ways to line up n people in a queue: 5 friends at a chai stall can stand in 5! = 120 different orders (5 choices for the first place, 4 for the second, and so on).
Think out loud
- Input: a whole number n ≥ 0. Output: n!, which grows extremely fast (20! already has 19 digits).
- Edge cases: 0 and 1 (both give 1), a big n.
The obvious attempt: a Number loop
function factorial(n) {
let result = 1;
for (let i = 2; i <= n; i++) result *= i;
return result;
}
for (const n of [0, 1, 5, 10, 18]) console.log(n, factorial(n));
console.log(25, factorial(25));
console.log(171, factorial(171));
Output:
0 1
1 1
5 120
10 3628800
18 6402373705728000
25 1.5511210043330986e+25
171 Infinity
Up to 18! everything is exact. 25! prints in scientific notation (e+25 means "× 10²⁵") with only 17 significant digits, while the real answer, 15511210043330985984000000, has 26 digits. And 171! is bigger than the largest Number JavaScript can hold at all (about 1.8 × 10³⁰⁸), so it becomes Infinity. The code is fine; the number type is the problem.
Number.MAX_SAFE_INTEGER
console.log(Number.MAX_SAFE_INTEGER);
console.log(2 ** 53 === 2 ** 53 + 1);
console.log(9007199254740993);
console.log(Number.isSafeInteger(6402373705728000), Number.isSafeInteger(121645100408832000));
Output:
9007199254740991
true
9007199254740992
true false
A JavaScript Number is a 64-bit floating-point number (IEEE 754 "double"). 53 of its bits hold the digits (the mantissa), the rest hold the exponent and the sign. So every whole number up to 2⁵³ - 1 = 9007199254740991 is exact; that is Number.MAX_SAFE_INTEGER. Past it, a Number can't hold every whole number, so it keeps the nearest one it can: 2 ** 53 + 1 rounds to 2 ** 53 (they compare equal), and typing 9007199254740993 gives 9007199254740992. Number.isSafeInteger(x) tells you whether x is a whole number inside the exact range: 18! is, 19! is not.
BigInt
Real-life picture. A shopkeeper's calculator with a 16-digit screen is fast but rounds long answers: that's a Number. Long multiplication on paper takes longer but keeps every digit: that's BigInt, a separate JavaScript type for exact whole numbers of any size. Write a BigInt by putting n after the digits (25n), or convert with BigInt(x).
First try: only result is a BigInt.
function factorial(n) {
let result = 1n;
for (let i = 2; i <= n; i++) result *= i;
return result;
}
console.log(factorial(25));
.../main.js:3
for (let i = 2; i <= n; i++) result *= i;
^
TypeError: Cannot mix BigInt and other types, use explicit conversions
result is a BigInt and i is a Number. JavaScript never mixes the two in arithmetic, because a silent conversion could lose digits (a Number can't hold a big BigInt exactly, and a BigInt can't hold a decimal). So it throws. Comparisons like i <= n are allowed between the types; arithmetic is not.
The fix: make i a BigInt too.
function factorial(n) {
let result = 1n;
for (let i = 2n; i <= BigInt(n); i++) result *= i;
return result;
}
for (const n of [0, 1, 5, 25]) console.log(n, factorial(n));
const f100 = factorial(100).toString();
console.log(f100.length, "digits");
console.log(f100.slice(0, 20) + "...");
console.log(typeof 5n, 10n / 3n);
Output:
0 1n
1 1n
5 120n
25 15511210043330985984000000n
158 digits
93326215443944152681...
bigint 3n
console.log shows BigInts with the n at the end. typeof 5n is "bigint". And 10n / 3n is 3n: BigInt division drops the remainder, because a BigInt can't hold decimals.
More BigInt facts (all run for real)
console.log(5n + 3n, 5n * 3n, 7n / 2n, 7n % 2n, 2n ** 64n);
console.log(5n == 5, 5n === 5, 5n < 6, typeof 5n);
console.log(Number(2n ** 64n), BigInt(Number.MAX_SAFE_INTEGER) + 2n);
8n 15n 3n 1n 18446744073709551616n
true false true bigint
18446744073709552000 9007199254740993n
+ - * / % **all work between two BigInts.5n == 5is true (same value),5n === 5is false (different types).Number(big)converts back, rounding if it's too big.
Three errors you will meet:
| Code | Error |
|---|---|
Math.sqrt(16n) |
TypeError: Cannot convert a BigInt value to a number (the Math functions take Numbers only) |
JSON.stringify({ big: 5n }) |
TypeError: Do not know how to serialize a BigInt (convert with .toString() first) |
BigInt(2.5) |
RangeError: The number 2.5 cannot be converted to a BigInt because it is not an integer |
Complexity
n multiplications: O(n) multiplications, O(1) extra variables. Strictly, each BigInt multiplication gets slower as the number gets longer (100! has 158 digits), so the real cost grows a little faster than n; in an interview, say "O(n) multiplications on growing numbers".
Q3: The n-th Fibonacci number
Problem. fib(0) = 0, fib(1) = 1, and every next number is the sum of the two before it:
n: 0 1 2 3 4 5 6 7 8 9 10
fib(n): 0 1 1 2 3 5 8 13 21 34 55
Return fib(n). It must be fast and exact for n = 80, and must not crash for n = 20000.
Think out loud
- The definition is a recurrence: fib(n) = fib(n - 1) + fib(n - 2).
- Edge cases: 0 and 1 (the starting values), n = 80 (past 2⁵³), n = 20000 (very deep).
The obvious attempt: recursion straight from the definition
A function that calls itself is recursion; n < 2 is the base case that stops it.
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
for (const n of [0, 1, 2, 10, 20]) console.log(n, fib(n));
let calls = 0;
function fibCount(n) { calls++; return n < 2 ? n : fibCount(n - 1) + fibCount(n - 2); }
fibCount(30);
console.log("calls for fib(30):", calls);
console.time("fib(40)");
console.log(fib(40));
console.timeEnd("fib(40)");
Output:
0 0
1 1
2 1
10 55
20 6765
calls for fib(30): 2692537
102334155
fib(40): 736.904ms
Right answers, but 2,692,537 calls for fib(30), and fib(40) takes most of a second. Each +1 to n makes it about 1.6 times slower, so fib(50) would take more than a minute.
Why. Draw the calls:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
...
fib(3) is computed twice, fib(2) three times, and lower values even more often. Every call splits into two calls, so the number of calls roughly doubles with each n: exponential time, O(2ⁿ) (more precisely about O(1.618ⁿ)). The space is O(n): the deepest chain of waiting calls.
Memoization
Real-life picture. A student who has to work out 17 × 23 every time it appears in the homework wastes time. Instead, write the answer in a notebook the first time, and look it up next time. In code the notebook is a Map from n to fib(n). This is memoization: caching the result of a function call so the same input is never computed twice.
const memo = new Map();
function fib(n) {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const value = fib(n - 1) + fib(n - 2);
memo.set(n, value);
return value;
}
console.time("fib(40)");
console.log(fib(40));
console.timeEnd("fib(40)");
console.log(fib(78));
console.log(fib(80), Number.isSafeInteger(fib(80)));
Output:
102334155
fib(40): 1.703ms
8944394323791464
23416728348467684 false
Each fib(k) is now computed once: O(n) time, O(n) space (the Map plus the call stack). But two new problems:
- fib(80) is not exact. The real value is 23416728348467685; the Number version ends in
684. fib(78) is the last Fibonacci number below 2⁵³. - Deep recursion crashes.
const memo = new Map();
function fib(n) {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const value = fib(n - 1) + fib(n - 2);
memo.set(n, value);
return value;
}
console.log(fib(20000));
.../main.js:3
if (n < 2) return n;
^
RangeError: Maximum call stack size exceeded
fib(20000) calls fib(19999), which calls fib(19998)... before any of them can return. Every call that is still waiting takes a slot on the call stack (the list of function calls that have started but not finished). Node's default stack holds roughly ten thousand frames of a function like this, so it overflows. (You could call fib(1), fib(2), ... in order to fill the memo from the bottom, but the loop below is simpler.)
The loop: O(n) time, O(1) space, exact
Keep only the last two numbers, as BigInts:
function fib(n) {
let a = 0n, b = 1n;
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
for (const n of [0, 1, 2, 10, 40]) console.log(n, fib(n));
console.log(80, fib(80));
console.log(100, fib(100));
console.log(fib(20000).toString().length, "digits");
Output:
0 0n
1 1n
2 1n
10 55n
40 102334155n
80 23416728348467685n
100 354224848179261915075n
4180 digits
Exact, and no recursion, so no stack limit. Building the answer from the smallest cases up like this is called bottom-up dynamic programming (memoization is the top-down form).
Complexity
| Version | Time | Extra space | Exact past fib(78)? | n = 20000 |
|---|---|---|---|---|
| Plain recursion | O(2ⁿ) | O(n) stack | no | never finishes |
| Memoization (Map) | O(n) | O(n) | no (with Number) | RangeError |
| Loop with BigInt | O(n) additions | O(1) variables | yes | 4180 digits |
Timings from one real run, for scale:
recursive 25: 4.783ms
recursive 30: 7.175ms
recursive 35: 67.536ms
memo 5000: 1.392ms
loop 5000: 2.438ms
Complexity summary
| Question | Approach | Time | Extra space |
|---|---|---|---|
| GCD | count down | O(min(a, b)) | O(1) |
| GCD | Euclid | O(log min(a, b)) | O(1) |
| LCM | a / gcd(a, b) * b |
O(log min(a, b)) | O(1) |
| Factorial | BigInt loop | O(n) multiplications | O(1) variables |
| Fibonacci | plain recursion | O(2ⁿ) | O(n) |
| Fibonacci | memoization | O(n) | O(n) |
| Fibonacci | BigInt loop | O(n) additions | O(1) variables |
Common mistakes (and the exact outputs)
| Mistake | Code | What you see | Why | Fix |
|---|---|---|---|---|
| Count down for the GCD | for (d = Math.min(a, b); d >= 1; d--) |
gcd(0, 5) → undefined; big: 1.518s |
loop never runs for 0; a billion steps for primes | Euclid |
| Multiply before dividing | a * b / gcd(a, b) |
246913577.99999997 |
a * b is past 2⁵³ and gets rounded |
a / gcd(a, b) * b |
| Factorial in a Number | let result = 1 |
1.5511210043330986e+25, Infinity |
exact only up to 2⁵³ - 1 | BigInt |
| Mixing BigInt and Number | 1n * i with i a Number |
TypeError: Cannot mix BigInt and other types, use explicit conversions |
no silent conversion | BigInt(i), or start i at 2n |
| Math on a BigInt | Math.sqrt(16n) |
TypeError: Cannot convert a BigInt value to a number |
Math takes Numbers |
convert, or write your own |
| JSON with a BigInt | JSON.stringify({ big: 5n }) |
TypeError: Do not know how to serialize a BigInt |
JSON has no BigInt type | .toString() first |
| Expecting decimals | 10n / 3n |
3n |
BigInt is whole numbers only | use Numbers for decimals |
| Plain recursive Fibonacci | fib(n - 1) + fib(n - 2) |
2,692,537 calls for fib(30) | the same values are recomputed | memo or a loop |
| Deep recursion | memoized fib(20000) |
RangeError: Maximum call stack size exceeded |
too many waiting calls | a loop |
Mini project: a fraction calculator
Add two fractions and print the answer in lowest terms, using today's GCD and LCM. Exact for any size, because it uses BigInt.
// Fraction calculator: a/b + c/d in lowest terms
function gcd(a, b) {
if (a < 0n) a = -a;
if (b < 0n) b = -b;
while (b !== 0n) [a, b] = [b, a % b];
return a;
}
function add(a, b, c, d) {
const den = b / gcd(b, d) * d; // the LCM of the denominators
const num = a * (den / b) + c * (den / d);
const g = gcd(num, den);
return `${num / g}/${den / g}`;
}
console.log(add(1n, 4n, 1n, 6n)); // 1/4 + 1/6
console.log(add(3n, 8n, 5n, 8n)); // 3/8 + 5/8
console.log(add(1n, 3n, -1n, 3n)); // 1/3 - 1/3
console.log(add(1n, 123456789n, 1n, 246913578n));
5/12
1/1
0/1
1/82304526
The LCM of the denominators is the "common denominator" from school: 1/4 + 1/6 = 3/12 + 2/12 = 5/12. Extend it: subtraction, multiplication, and reading the fractions from input.
Your turn: the LCM of 1 to n (solution)
Problem. Find the smallest number that every number from 1 to n divides. n = 10 → 2520, n = 20 → 232792560.
Idea. The LCM of a list is built up two at a time: lcm(1..n) = lcm(lcm(1..n-1), n). Start at 1 and fold in each number with result / gcd(result, i) * i.
Solution
With Numbers, the answer for n = 50 is already too big to be exact:
function gcd(a, b) {
while (b !== 0) [a, b] = [b, a % b];
return a;
}
let r = 1;
for (let i = 2; i <= 50; i++) r = r / gcd(r, i) * i;
console.log(r, Number.isSafeInteger(r));
1.8523376382441352e+28 false
So use BigInt (and a GCD that works on BigInts: compare with 0n):
function gcd(a, b) {
while (b !== 0n) [a, b] = [b, a % b];
return a;
}
function lcmUpTo(n) {
let result = 1n;
for (let i = 2n; i <= BigInt(n); i++) result = result / gcd(result, i) * i;
return result;
}
for (const n of [1, 10, 20, 50]) console.log(n, lcmUpTo(n));
1 1n
10 2520n
20 232792560n
50 3099044504245996706400n
Look closely: the Number version printed 1.85 × 10²⁸, the BigInt version 3.1 × 10²¹? The Number version is not just rounded, it is wrong: once r passes 2⁵³, r % i is computed on a rounded value, so the GCD is wrong and extra factors get multiplied in. Inexact numbers don't only lose digits; they can make every later step wrong.
Complexity: n - 1 GCDs, each O(log) steps: about O(n log n) operations on growing BigInts.
Practice questions (with solutions)
1. Simplify a fraction (18/48 → 3/8; the sign goes on top; a zero denominator is an error).
Solution
function gcd(a, b) {
a = Math.abs(a); b = Math.abs(b);
while (b !== 0) [a, b] = [b, a % b];
return a;
}
function simplify(num, den) {
if (den === 0) throw new RangeError("denominator is 0");
const g = gcd(num, den);
let n = num / g, d = den / g;
if (d < 0) { n = -n; d = -d; }
return `${n}/${d}`;
}
console.log(simplify(18, 48), simplify(10, 5), simplify(-6, 8), simplify(6, -8), simplify(0, 7));
try { simplify(1, 0); } catch (e) { console.log(e.name + ": " + e.message); }
3/8 2/1 -3/4 -3/4 0/1
RangeError: denominator is 0
Math.abs keeps the GCD positive even for negative inputs (-6 % 8 is -6 in JavaScript, the remainder takes the sign of the left side).
2. The sum of the digits of 100!
Solution
let f = 1n;
for (let i = 2n; i <= 100n; i++) f *= i;
let sum = 0;
for (const ch of f.toString()) sum += Number(ch);
console.log(sum);
648
BigInt keeps all 158 digits exact; toString() turns it into text we can walk digit by digit (episode 1's % 10 loop works too, with 10n).
3. The number of trailing zeros of n!, without computing n!
Solution
Each trailing zero is a factor 10 = 2 × 5. There are always more 2s than 5s, so count the 5s: every multiple of 5 gives one, every multiple of 25 one more, every multiple of 125 one more...
function trailingZeros(n) {
let count = 0;
for (let p = 5; p <= n; p *= 5) count += Math.floor(n / p);
return count;
}
for (const n of [4, 5, 10, 25, 100, 1000]) console.log(n, trailingZeros(n));
let f = 1n;
for (let i = 2n; i <= 100n; i++) f *= i;
console.log(f.toString().length - f.toString().replace(/0+$/, "").length);
4 0
5 1
10 2
25 6
100 24
1000 249
24
The last line checks the answer for 100! with BigInt: 24. Time O(log₅ n), space O(1).
4. A safe factorial that rejects negative and decimal inputs.
Solution
function factorial(n) {
if (!Number.isInteger(n) || n < 0) throw new RangeError("n must be a whole number >= 0");
let result = 1n;
for (let i = 2n; i <= BigInt(n); i++) result *= i;
return result;
}
console.log(factorial(20));
try { factorial(-3); } catch (e) { console.log(e.name + ": " + e.message); }
try { factorial(2.5); } catch (e) { console.log(e.name + ": " + e.message); }
2432902008176640000n
RangeError: n must be a whole number >= 0
RangeError: n must be a whole number >= 0
Without the check, BigInt(2.5) would throw its own RangeError: The number 2.5 cannot be converted to a BigInt because it is not an integer, and a negative n would quietly return 1n.
5. Climbing stairs. You climb a staircase taking 1 or 2 steps at a time. In how many ways can you climb n steps?
Solution
The last move is either 1 step (from n - 1) or 2 steps (from n - 2), so ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1. It's Fibonacci shifted by one: ways(n) = fib(n + 1).
function climbWays(n) {
let a = 1, b = 1;
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
for (const n of [1, 2, 3, 4, 5, 10]) console.log(n, climbWays(n));
1 1
2 2
3 3
4 5
5 8
10 89
O(n) time, O(1) space. One of the most-asked interview questions; spotting the Fibonacci recurrence is the whole trick.
Quick quiz
1. (From the video.) What does this print?
console.log(7n / 2n, 2 ** 53 + 1 === 2 ** 53);
(A) 3.5 false (B) 3n true (C) 3.5n true (D) TypeError
Answer
(B) 3n true. BigInt division drops the remainder, so 7n / 2n is 3n. And 2 ** 53 + 1 can't be stored exactly as a Number, so it rounds back to 2 ** 53, and the comparison is true.
2. What does console.log(5n === 5, 5n == 5) print?
Answer
false true. Same value, different types: === checks the type too.
3. How many steps does Euclid take for gcd(1071, 462)?
Answer
Three: (1071, 462) → (462, 147) → (147, 21) → (21, 0). The GCD is 21.
4. Which is the biggest Fibonacci number a Number stores exactly: fib(78), fib(80) or fib(100)?
Answer
fib(78) = 8944394323791464. fib(79) = 14472334024676221 is already past 2⁵³ = 9007199254740992.
Interview questions
- Explain Euclid's algorithm and why it works. gcd(a, b) = gcd(b, a % b): any common divisor of a and b also divides a % b = a - q·b, and the other way round, so both pairs have the same common divisors. Stop when b is 0.
- What is its time complexity? O(log min(a, b)): the larger number at least halves every two steps.
- How do you compute the LCM without overflow?
a / gcd(a, b) * b: divide first. lcm(a, 0) = 0. - What is
Number.MAX_SAFE_INTEGERand why is it 2⁵³ - 1? A Number is a 64-bit IEEE 754 double with 53 bits of precision; every whole number up to 2⁵³ - 1 is exact, after that only some are. - What is BigInt? When would you use it? A type for exact whole numbers of any size (
123n,BigInt(x)): factorials, big Fibonacci numbers, IDs from databases bigger than 2⁵³, cryptography. - What are the limits of BigInt? No decimals (
7n / 2nis3n), can't mix with Number in arithmetic,Mathfunctions don't accept it,JSON.stringifythrows, and it is slower than Number. - Why is the naive recursive Fibonacci slow? It recomputes the same subproblems; the call tree has about 1.6ⁿ nodes: exponential time.
- What is memoization? Caching a function's results by input so each input is computed once. It turns the exponential Fibonacci into O(n) time and O(n) space.
- Top-down vs bottom-up? Top-down: recursion plus a memo, computes only what's needed. Bottom-up: a loop from the smallest cases, no recursion and often O(1) space (the Fibonacci loop).
- What causes
RangeError: Maximum call stack size exceeded? Too many nested calls that haven't returned yet: deep or infinite recursion. Fix it with a loop, or with a base case that is really reached. - What is 0! and why? 1: there is exactly one way to arrange zero things, and it keeps n! = n × (n - 1)! true for n = 1.
Glossary
| Term | Meaning | Example |
|---|---|---|
| GCD (greatest common divisor) | The biggest number that divides both a and b; also called HCF | gcd(48, 18) = 6 |
| HCF | Highest common factor: another name for the GCD | HCF(12, 8) = 4 |
| LCM (least common multiple) | The smallest positive number that both a and b divide | lcm(4, 6) = 12 |
| Coprime | Two numbers whose GCD is 1 | 7 and 13 |
| Euclid's algorithm | Finds the GCD by repeating gcd(a, b) = gcd(b, a % b) until b is 0 | (48, 18) → (18, 12) → (12, 6) → (6, 0) |
Remainder (%) |
What's left after division; takes the sign of the left side | 48 % 18 is 12, -6 % 8 is -6 |
| Array destructuring | Assigning the items of an array to variables in one step | [a, b] = [b, a % b] |
undefined |
The value of a missing return, or of a variable with no value | a function with no return |
| Factorial (n!) | 1 × 2 × ... × n; 0! = 1 | 5! = 120 |
| Scientific notation | A number as digits × a power of 10 | 1.55e+25 = 1.55 × 10²⁵ |
Infinity |
The Number for values too big to store | factorial(171) |
| Floating-point number | A number stored as digits plus an exponent, so the point "floats" | every JavaScript Number |
| IEEE 754 double | The 64-bit floating-point format JavaScript Numbers use: 53 bits of precision | 0.1 + 0.2 is 0.30000000000000004 |
| Mantissa | The part of a floating-point number that holds the digits | 53 bits in a double |
Number.MAX_SAFE_INTEGER |
The biggest whole number a Number holds exactly: 2⁵³ - 1 | 9007199254740991 |
Number.isSafeInteger(x) |
True if x is a whole number in the exact range | Number.isSafeInteger(2 ** 53) is false |
| BigInt | A type for exact whole numbers of any size; written with an n |
25n, BigInt(25) |
TypeError |
An error for a value of the wrong type | Cannot mix BigInt and other types |
RangeError |
An error for a value outside the allowed range | Maximum call stack size exceeded |
| Fibonacci numbers | 0, 1, then each is the sum of the two before | 0 1 1 2 3 5 8 13 |
| Recurrence | A formula that defines a value from earlier values | fib(n) = fib(n - 1) + fib(n - 2) |
| Recursion | A function that calls itself | fib(n - 1) inside fib |
| Base case | The input where recursion stops | if (n < 2) return n; |
| Call stack | The list of function calls that have started but not finished | fib(20000) → fib(19999) → ... |
| Stack overflow | The call stack runs out of room | RangeError: Maximum call stack size exceeded |
| Memoization | Storing results by input so each is computed once | memo.set(n, value) |
Map |
A collection of key → value pairs | memo.get(40) |
| Top-down | Recursion plus a memo | memoized fib |
| Bottom-up | A loop from the smallest cases up | the Fibonacci loop |
| Dynamic programming | Solving a problem from the answers of its overlapping smaller problems | Fibonacci, climbing stairs |
| Exponential time (O(2ⁿ)) | The work roughly doubles each time n grows by 1 | plain recursive fib |
| O(log n) | The steps grow like the number of digits: halving each time | Euclid |
| O(n) | The steps grow in proportion to n | the factorial loop |
| O(1) | A fixed amount, whatever the input | two variables a, b |
| Edge case | An input at the boundary that often breaks code | gcd(0, 5), fib(0), 25! |
Summary
- GCD: Euclid's
gcd(a, b) = gcd(b, a % b)until b is 0. O(log n). Counting down is O(n) and returnsundefinedfor a zero. - LCM:
a / gcd(a, b) * b, divide first;a * b / gcdgave246913577.99999997. - Numbers are exact only up to 2⁵³ - 1 (
Number.MAX_SAFE_INTEGER). Past it, digits get rounded:2 ** 53 + 1 === 2 ** 53istrue. - BigInt (
25n,BigInt(x)) is exact for whole numbers of any size; no decimals, and never mixed with Number (TypeError: Cannot mix BigInt and other types). - Fibonacci: plain recursion is O(2ⁿ) (2.7 million calls for fib(30)); memoization with a
Mapis O(n) but deep recursion throwsRangeError: Maximum call stack size exceeded; a loop with two BigInt variables is O(n) time, O(1) space and exact. - Always test zero, the smallest cases and a huge input.
Next episode: Number questions IV: decimal to binary and back, counting set bits, and a one-line power of two check with n & (n - 1), plus the 32-bit trap in every bitwise operator.