Module 4 · if, switch and Loops

Full Programs: From FizzBuzz to a Prime Sieve

FreeReadingLesson 3 of 9

In this lesson

Write seven complete programs on the fixed starter, from a FizzBuzz variant to a prime sieve, each with its real output.
Explain why the combined test comes first in an if chain, and why a prime check can stop at the square root.
Track a running answer in one pass over the input, starting each value where the first item cannot fool it.

Many junior developer interviews still open with the same small task. Count from 1 upwards. Say "Fizz" for a multiple of 3, "Buzz" for a multiple of 5, and "FizzBuzz" for both. It is called FizzBuzz, and it is not a maths test. It checks whether you can put an if inside a loop and get the order right. This lesson does that honestly, then grows six more programs, up to the ones a working programmer writes.

The shape all seven programs share

Every program here has four steps. It reads with the starter's next() and nextInt(), loops over the input, decides something for each value, and pushes a line to out. The last line of the starter prints everything at once. Module 1 showed two loop shapes to use as given, and lessons 01 and 02 explained them. These programs use both.

Two ways to walk the input

const n = nextInt();
for (let i = 0; i < n; i++) { ...read one value... }

let token = next();
while (token !== undefined) {
  ...use token...
  token = next();
}

The for loop fits input that says how many values come: "the first line holds n".
The while loop fits input that runs until it ends. next() returns undefined once the tokens run out.
break leaves either loop at once, and continue skips to the next pass. Lesson 02 showed both.

FizzBuzz, honestly

Zara plays a party version of the game. A multiple of 3 is "Fizz", a multiple of 7 is "Bazz", and a multiple of both is "FizzBazz". Here is the if chain for the numbers 12 to 21. Read the order of the tests.

const out = [];
for (let i = 12; i <= 21; i++) {
  if (i % 3 === 0 && i % 7 === 0) {
    out.push("FizzBazz");
  } else if (i % 3 === 0) {
    out.push("Fizz");
  } else if (i % 7 === 0) {
    out.push("Bazz");
  } else {
    out.push(i);
  }
}
console.log(out.join("\n"));

Fizz
13
Bazz
Fizz
16
17
Fizz
19
20
FizzBazz

An if chain runs the first branch whose test is true and skips the rest. 21 passes the test i % 3 === 0, so a chain that asks about 3 first prints "Fizz" and never reaches the combined test. So the most specific test goes first. Common mistake 1 shows the wrong order and its real output.

The chain has a weakness. With two words it needs four branches; with three words it needs eight, one for each mix. The honest fix builds the word instead of choosing it.

Example 1: build the word

New here: three separate if statements that each add a piece, with no else, and word || i to fall back on the number. Zara adds "Boom" for multiples of 11.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
for (let k = 0; k < n; k++) {
  const i = nextInt();
  let word = "";
  if (i % 3 === 0) {
    word += "Fizz";
  }
  if (i % 7 === 0) {
    word += "Bazz";
  }
  if (i % 11 === 0) {
    word += "Boom";
  }
  out.push(word || i);
}

console.log(out.join("\n"));

10
FizzBazz
Boom
FizzBoom
BazzBoom
FizzBazzBoom
Bazz
Fizz

That output is for the input 8, then 10 21 22 33 77 231 7 9. 231 is 3 times 7 times 11, so all three tests add their piece. When no test passes, word is still "", which is falsy, so || gives the number (Module 2). Order no longer matters, and a fourth word is one more line.

Run in Compiler

A loop that stops for two reasons

Some loops end on a count, and some end on an event. A guessing game has both: you may run out of tries, or you may guess right. The loop's own test handles one reason, and break handles the other.

Example 2: a guessing game with a limit

New here: a while loop whose test is the limit, with break for the right guess and for input that ends early. Alice picks a secret and allows a fixed number of tries.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const secret = nextInt();
const limit = nextInt();
let tries = 0;
let found = false;

while (tries < limit) {
  const token = next();
  if (token === undefined) {
    break;
  }
  tries++;
  const guess = Number(token);
  if (guess === secret) {
    found = true;
    break;
  }
  out.push(guess + " is too " + (guess < secret ? "low" : "high"));
}

if (found) {
  out.push("got it in " + tries);
} else {
  out.push("no luck after " + tries + ", it was " + secret);
}

console.log(out.join("\n"));

50 is too high
25 is too low
37 is too low
43 is too high
got it in 5

That output is for the input 42 5, then 50 25 37 43 42 10. The fifth guess is right, just inside the limit, so the 10 is never read. The flag found remembers why the loop ended, because after the loop both reasons look the same. Change the limit to 4 and the last line becomes no luck after 4, it was 42.

Run in Compiler

A grid from two loops

A loop inside another loop is a nested loop. The inner loop runs all its passes for each single pass of the outer one. So for a grid of 6 rows and 6 columns, the inner body runs 36 times.

Example 3: a multiplication grid

New here: nested for loops, and padStart to line the columns up. String(x).padStart(w) adds spaces on the left until the text is w characters long; Module 3 covers it.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
const width = String(n * n).length + 1;

for (let row = 1; row <= n; row++) {
  let line = "";
  for (let col = 1; col <= n; col++) {
    line += String(row * col).padStart(width);
  }
  out.push(line);
}

console.log(out.join("\n"));

  1  2  3  4  5  6
  2  4  6  8 10 12
  3  6  9 12 15 18
  4  8 12 16 20 24
  5 10 15 20 25 30
  6 12 18 24 30 36

That output is for the input 6. The widest number is n * n, 36, which has 2 characters, so every cell is 3 wide with one space to spare. line is created fresh inside the outer loop, so each row starts empty. The two counters have different names, row and col; Common mistake 3 shows what one name for both does.

Run in Compiler

Is it prime? Stop at the square root

A prime is a whole number above 1 whose only divisors are 1 and itself. To test n, try each divisor d from 2 upwards. Divisors come in pairs: if d divides n, so does n / d. One of the two is at most the square root of n. So the loop can stop once d * d passes n, and it can stop at once when a divisor turns up.

Example 4: a prime check that exits early

New here: trial division with d * d <= n as the loop's test and break at the first divisor. The program also prints the pair it found.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const count = nextInt();
for (let k = 0; k < count; k++) {
  const n = nextInt();
  let divisor = 0;
  for (let d = 2; d * d <= n; d++) {
    if (n % d === 0) {
      divisor = d;
      break;
    }
  }
  if (n < 2) {
    out.push(n + ": neither prime nor composite");
  } else if (divisor === 0) {
    out.push(n + ": prime");
  } else {
    out.push(n + ": not prime, " + divisor + " x " + n / divisor);
  }
}

console.log(out.join("\n"));

1: neither prime nor composite
2: prime
91: not prime, 7 x 13
97: prime
7919: prime
1000001: not prime, 101 x 9901

That output is for the input 6, then 1 2 91 97 7919 1000001. For 2 the inner loop never runs, because 2 times 2 is already past 2. For 7919 it tries d from 2 to 88, since 89 times 89 is 7921. Without the square-root stop it would try about 7,900 divisors.

Run in Compiler

The sieve: cross out instead of divide Intermediate

To find every prime up to n, testing each number alone repeats a lot of work. The sieve of Eratosthenes, named after a Greek scholar of about 240 BC, turns the job around. Write down every number, then cross out the multiples of each prime you meet. Whatever is never crossed out is prime.

The program keeps one true or false flag per number, in an array. new Array(n + 1).fill(true) makes n + 1 slots, numbered 0 to n, all set to true. isPrime[m] reads slot m, and isPrime[m] = false crosses it out. Module 7 teaches arrays properly; here the array is a row of flags.

Example 5: the sieve up to 30

New here: an array of flags, an inner loop that steps by p with m += p, and continue to skip a number already crossed out.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;

for (let p = 2; p * p <= n; p++) {
  if (!isPrime[p]) {
    continue;
  }
  let crossed = "";
  for (let m = p * p; m <= n; m += p) {
    if (isPrime[m]) {
      isPrime[m] = false;
      crossed += " " + m;
    }
  }
  out.push("crossed by " + p + ":" + crossed);
}

let primes = "";
for (let i = 2; i <= n; i++) {
  if (isPrime[i]) {
    primes += " " + i;
  }
}
out.push("primes:" + primes);

console.log(out.join("\n"));

crossed by 2: 4 6 8 10 12 14 16 18 20 22 24 26 28 30
crossed by 3: 9 15 21 27
crossed by 5: 25
primes: 2 3 5 7 11 13 17 19 23 29

That output is for the input 30, and it matches the picture line for line. Each prime p starts crossing at p * p, because every smaller multiple has a smaller factor that already crossed it. 4 is skipped by continue, since 2 crossed it. The sieve does no division at all, which is why it wins when you need every prime up to n.

Run in Compiler

A menu with switch

A switch compares one value with a list of case values, using ===, and jumps to the first match. Lesson 02 showed its one trap: without break, the run falls through into the next case. It also showed the one honest use of that fall-through: several cases that share one action.

Example 6: Kenji's coffee kiosk

New here: a switch inside a while loop, with two cases grouped on one action. Each word is an item, and pay prints the bill and starts a new one.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let total = 0;
let token = next();

while (token !== undefined) {
  switch (token) {
    case "tea":
      total += 20;
      break;
    case "coffee":
      total += 50;
      break;
    case "cake":
    case "muffin":
      total += 40;
      break;
    case "pay":
      out.push("paid " + total);
      total = 0;
      break;
    default:
      out.push("no item " + token);
  }
  token = next();
}

if (total > 0) {
  out.push("unpaid " + total);
}

console.log(out.join("\n"));

paid 110
no item juice
paid 60
unpaid 50

That output is for the input tea cake coffee pay muffin juice tea pay coffee. cake and muffin share a price, so the empty case "cake": falls through on purpose. default catches every word with no case. Note that break inside a switch leaves the switch, not the loop around it.

Run in Compiler

Statistics in one pass

A running value is one you update as each item arrives, like a total. With running values, a program reads each item once and keeps nothing else. Each running value needs a safe start. A count starts at 0. A largest-so-far starts at -Infinity, which every real number beats, or at the first item itself.

Example 7: a week of temperatures

New here: several running values in one loop, and previous to remember the last item. David's weather log lists one temperature per day, until the input ends.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let count = 0;
let highest = -Infinity;
let highestDay = 0;
let biggestRise = 0;
let frostDays = 0;
let previous = 0;

let token = next();
while (token !== undefined) {
  const t = Number(token);
  count++;
  if (t > highest) {
    highest = t;
    highestDay = count;
  }
  if (count > 1 && t - previous > biggestRise) {
    biggestRise = t - previous;
  }
  if (t < 0) {
    frostDays++;
  }
  previous = t;
  token = next();
}

out.push("days " + count);
out.push("highest " + highest + " on day " + highestDay);
out.push("biggest rise " + biggestRise);
out.push("frost days " + frostDays);

console.log(out.join("\n"));

days 7
highest 12 on day 7
biggest rise 13
frost days 2

That output is for the input 3 -2 4 9 7 -1 12. The rise from -1 to 12 on the last day is 13. count > 1 guards the first day, which has no day before it. > rather than >= keeps the first day a high was reached. A week that only gets colder reports a biggest rise of 0, which is a choice this program made.

Run in Compiler

Where this is used

Hiring screens. Imran Ghory's 2007 blog post proposed FizzBuzz to filter job candidates. Jeff Atwood's "Why Can't Programmers.. Program?" the same year made it famous.
OpenSSL. Before its probabilistic Miller-Rabin test, OpenSSL divides a candidate prime by a table of small primes. A cheap early exit throws out most candidates first.
The Unix wc tool. It counts the lines, words and bytes of a file in one pass, with running counts like Example 7's.
Redux. Its documentation writes a reducer as a switch on action.type, with one case per action and a default, the same shape as Kenji's kiosk.

Common mistakes

1. The combined test last.

const out = [];
for (let i = 19; i <= 21; i++) {
  if (i % 3 === 0) {
    out.push("Fizz");
  } else if (i % 7 === 0) {
    out.push("Bazz");
  } else if (i % 3 === 0 && i % 7 === 0) {
    out.push("FizzBazz");
  } else {
    out.push(i);
  }
}
console.log(out.join("\n"));

19
20
Fizz

No error, and 21 says "Fizz". The first test already matched 21, so the combined branch can never run. Put the most specific test first, or build the word as Example 1 does. You will make this mistake because you write the rules in the order the game states them.

2. A prime check that calls 1 a prime.

const n = 1;
let prime = true;
for (let d = 2; d * d <= n; d++) {
  if (n % d === 0) {
    prime = false;
    break;
  }
}
console.log(n + (prime ? " is prime" : " is not prime"));

1 is prime

The loop never runs for 1, so nothing sets the flag to false. Start with let prime = n >= 2;, so 0, 1 and negative numbers fail before the loop. You will miss it because you test with 7 and 9, never with 1.

3. One counter name for both loops.

const out = [];
for (let i = 1; i <= 3; i++) {
  let line = "";
  for (let i = 1; i <= 3; i++) {
    line += String(i * i).padStart(3);
  }
  out.push(line);
}
console.log(out.join("\n"));

  1  4  9
  1  4  9
  1  4  9

No error. The inner let i is a new variable that hides the outer one, so i * i uses the column twice. Every row comes out the same. Name the counters for what they count, row and col. You will do this because i is the name your fingers type for any loop.

4. A running minimum that starts at 0.

const temps = [5, 8, 3, 9];
let lowest = 0;
for (const t of temps) {
  if (t < lowest) {
    lowest = t;
  }
}
console.log("lowest " + lowest);

lowest 0

No error, and 0 is not even in the list. No temperature is below the starting 0, so it never moves. Start at Infinity, or at the first item. You will start at 0 because a total starts there, and a minimum feels like the same kind of thing.

Brain teaser

const n = 97;
let tests = 0;
for (let d = 2; d * d <= n; d++) {
  tests++;
  if (n % d === 0) {
    break;
  }
}
console.log(tests);

How many numbers does this trial division test for n = 97? And how many after you change the first line to const n = 100;? Work both out on paper before you run it.

For 97, find the largest d with d * d <= 97, and remember that a prime never triggers the break. For 100, ask which d divides it first.

Exercise 1Easy

Bob has an interview tomorrow, and he wants the classic version right, every line of it.

Input. One whole number n.

Output. n lines, one for each i from 1 to n. Print FizzBuzz when i is a multiple of both 3 and 5, Fizz when only of 3, Buzz when only of 5, otherwise i itself.

Constraints. 1 <= n <= 100000.

Sample. Input 15 gives 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14 and FizzBuzz on 15 lines.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Graded as fizzbuzz. The hidden tests try n = 1, values of n on either side of a multiple of 15, and the largest n.

Run in Compiler

Exercise 2Medium

Maria keeps a list of whole numbers and wants its summary in one pass, the way wc counts a file.

Input. n, then n whole numbers.

Output. Four lines: count and n; min and the smallest; max and the largest; average and the sum divided by n, as JavaScript prints the number (what String() gives).

Constraints. 1 <= n <= 100000; -1000000000 <= each number <= 1000000000, so the sum is an exact whole number.

Sample. Input 5, then 4 -3 12 7 1, gives count 5, min -3, max 12 and average 4.2 on four lines.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Graded as min-max-average. The hidden tests include a list of one number, lists where every number is negative, and the largest values allowed.

Run in Compiler

Exercise 3Medium

Alice's game drops the limit from Example 2. The player keeps guessing until the secret is found or the guesses run out.

Input. The secret s, then the guesses, until the input ends. There may be no guesses at all.

Output. One line for each guess in order. When it is the secret, print correct in k, where k counts the guesses read, this one included. Then stop, ignoring any later guesses. When the secret is higher, print higher; when it is lower, print lower. If the input ends without a right guess, print not found after k, with k the guesses read, possibly 0.

Constraints. 1 <= s <= 1000000000; at most 100000 guesses, each from 1 to 1000000000.

Sample. Input 50, then 25 75 50 10, gives higher, lower and correct in 3 on three lines.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Graded as guessing-game. The hidden tests include input with no guesses, a right first guess, and guesses after the right one.

Run in Compiler

Exercise 4Hard

Kenji wants to know how many primes there are up to a large n, and the last one before it.

Input. One whole number n.

Output. Two lines: how many primes are less than or equal to n, and the largest of them, or none when there is none (n < 2).

Constraints. 1 <= n <= 15000000.

Sample. Input 30 gives 10 and 29 on two lines.

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Graded as count-primes. The hidden tests run from n = 1 up to the largest n allowed.

Run in Compiler

Common doubts

Why d * d <= n and not d <= Math.sqrt(n)?

Both stop at the same place for the numbers in this lesson. d * d stays in whole numbers, so no rounding of a square root can surprise you. Kenji likes that it skips a function call, but exactness is the real reason.
Why push every line to out and print once?

One console.log per line gets slow past a few thousand lines, and the judge's tests can have a hundred thousand. Collecting lines and printing once with join avoids that. It also keeps every program in the same shape.
Is the sieve always better than trial division?

No. To test one number, trial division is enough and needs no memory. The sieve wins when you need every prime up to n. It keeps one flag per number, so n = 15,000,000 means fifteen million flags.
Can a switch compare strings?

Yes. It compares with ===, so "tea" matches only the exact text "tea". A token "Tea" with a capital goes to default.

Key takeaways

In an if chain the first true test wins, so the most specific test goes first; building the word avoids the order problem.
A loop can stop for two reasons: its own test, and a break. A flag records which one happened.
Nested loops multiply: n rows of n columns run the inner body n times n times. Give each counter its own name.
A prime check stops at d * d <= n and at the first divisor. The sieve crosses out multiples to find every prime up to n.
Running values read the input once; start a minimum or maximum where the first item cannot fool it.
Go deeper: Under the Hood, loops as jumps, the iterator protocol and a loop lab (Pro).

Next, Kenji's review says "use forEach everywhere" on a loop that must stop early, and lesson 04 picks the loop from three questions.

End of lesson 3

Mark it done, and your progress moves with you.

Next: Which Loop, and When switch Beats if

Next lesson