SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 3
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 3 of 30

Number questions III

GCD and LCM (Euclid)factorial and Number.MAX_SAFE_INTEGER (BigInt as the fix)n-th Fibonacci (loop vs naive recursion vs memo)

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.518s are 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 product a * b is 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.

  1. gcd(0, 5): the smaller number is 0, so d starts at 0, the condition d >= 1 is false straight away, the loop never runs, and the function falls off the end. A function that ends without return gives undefined.
  2. 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 == 5 is true (same value), 5n === 5 is 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:

  1. 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⁵³.
  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

  1. 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.
  2. What is its time complexity? O(log min(a, b)): the larger number at least halves every two steps.
  3. How do you compute the LCM without overflow? a / gcd(a, b) * b: divide first. lcm(a, 0) = 0.
  4. What is Number.MAX_SAFE_INTEGER and 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.
  5. 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.
  6. What are the limits of BigInt? No decimals (7n / 2n is 3n), can't mix with Number in arithmetic, Math functions don't accept it, JSON.stringify throws, and it is slower than Number.
  7. Why is the naive recursive Fibonacci slow? It recomputes the same subproblems; the call tree has about 1.6ⁿ nodes: exponential time.
  8. 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.
  9. 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).
  10. 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.
  11. 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 returns undefined for a zero.
  • LCM: a / gcd(a, b) * b, divide first; a * b / gcd gave 246913577.99999997.
  • Numbers are exact only up to 2⁵³ - 1 (Number.MAX_SAFE_INTEGER). Past it, digits get rounded: 2 ** 53 + 1 === 2 ** 53 is true.
  • 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 Map is O(n) but deep recursion throws RangeError: 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.