Learn JavaScript

Lesson 7 of 9 · if, switch and Loops

Module 4 · if, switch and Loops

Problems: if, switch and Loops

FreeProblems

In this lesson

  • Read an input of unknown length in the three ways these ten need: a count first, a sentinel, or until the input runs out.
  • Pick the loop shape for each problem and stop it the moment the answer is known, with break, a flag or a labelled break.
  • Test the hidden tests' edges before you submit: n = 1, a value on a boundary, an empty input and the largest size.

Ten problems, graded against hidden tests on Node 22, the same JavaScript the Playground runs. You met every one of them in this module. steps-goal was in lesson 01, and letter-grade, day-name and sum-until-zero were in lesson 02. Lesson 03 held fizzbuzz, min-max-average, guessing-game and count-primes, lesson 04 held till-commands, and first-pair-sum was in the CP and Interview Pack.

Problems 1, 2 and 5 (steps-goal, letter-grade and fizzbuzz) are free for everyone. The other seven are Pro problems: locks per problem arrive in a later release, and until then all ten are open. The module test has two problems, fizzbuzz and min-max-average, so both are worth solving here first.

Bob writes the loop, runs the sample and submits. Zara first feeds her program n = 1, an input with no guesses and a mark of exactly 90. In this set the hidden tests live at the ends of the loops. They try the first pass, the last pass and the pass where the loop should have stopped.

Three ways a loop knows the list is over

The starter splits the whole input into tokens. A token is a piece of text between spaces or line breaks. next() hands you the next token, and nextInt() turns it into a number. A loop that reads tokens needs one more thing: a way to know when to stop reading.

These ten problems use three ways. Most give a count first: read n, then loop n times. sum-until-zero uses a sentinel, a special value that marks the end and is not part of the data, here the first 0. guessing-game and till-commands read until the input ends, with no count and no sentinel.

How does a program see the end of the input? Once the tokens run out, next() returns undefined, and nextInt() returns NaN. This small program shows both with an array of two tokens in place of the input.

const tokens = ["7", "3"];
let at = 0;
const next = () => tokens[at++];

console.log(next(), next(), next());
console.log(Number(undefined));

7 3 undefined
NaN

So a loop that reads until the input ends tests the token itself: while (token !== undefined). A loop that reads one token too many sees undefined, turns it into NaN, and spoils any sum it touches.

Three ways a loop knows the list is over Three ways a loop knows the list is over A count first steps-goal, fizzbuzz 3 n 8 2 5 read exactly n, then stop A sentinel sum-until-zero 5 -2 7 0 the end 4 4 never read Until the input ends guessing-game, till 50 25 75 undefined next() past the last token Solid boxes: tokens the loop reads. Dashed boxes: what it must never treat as data.

All three rows end on a box the loop must recognise and not use as data. The count says where that box is in advance; the sentinel and undefined tell you only when you reach them.

The loop shapes in these ten

Each problem needs one of four loop shapes. Lesson 04's flowchart picks them from the same questions: do you know the count, and must you stop early?

  • A counted for loop. steps-goal, letter-grade, day-name, fizzbuzz and min-max-average read n first, so the loop runs exactly n times.
  • A while loop with a sentinel. sum-until-zero reads one number before the loop, and the loop's test checks it before it is used.
  • A while loop until the input ends. guessing-game and till-commands test the token for undefined, and both can also stop early.
  • Two nested loops. count-primes crosses out multiples inside a loop over the numbers, and first-pair-sum tries every pair.

Inside the loops, the decisions are an if and else if chain (letter-grade, fizzbuzz) or a switch (day-name, till-commands). Both stop at the first match, so the order of the tests is part of the answer.

Stopping early: break, a flag and a label

Three problems end before the input does. guessing-game stops at the right guess, till-commands stops at close, and first-pair-sum stops at the first pair. Each one needs a different tool.

break leaves the nearest loop or switch, and only that one. Inside a switch that sits inside a loop, a break leaves the switch and the loop goes on. So a stop that lives inside a switch needs a flag, a boolean the loop's test reads, or a label on the loop.

A label is a name with a colon in front of a loop, such as search:. break search; then leaves that loop, even from inside a loop nested in it. Use it when one answer ends two loops at once. Example 3 below shows it on a different problem.

The edges the hidden tests try

Every problem has 11 to 15 hidden tests, and every test file stays under 1 MiB. They run from the smallest input to the largest the constraints allow that fits the judge. Between those two sit the edges this module warned you about. The table names them, so you can try them first.

ProblemAccessTestsWhat the hidden tests try
steps-goalFree12n = 1, a goal of 0 and of 100000, days exactly on the goal and one step short, 100000 days
letter-gradeFree1159 and 60, 89 and 90, 0 and 100, -1 and 101, -1000 and 1000, every mark from -5 to 105, 100000 marks
day-namePro11all seven days in both orders, 0, 8 and negative numbers, -1000 and 1000, 100000 numbers
sum-until-zeroPro12a 0 first, numbers after the 0, several 0s, numbers across several lines, 100000 numbers of 1000000
fizzbuzzFree13n = 1, 2, 3 and 5, 14 and 16 on either side of 15, 30 and 45, n = 100000
min-max-averagePro14n = 1, all negative, all positive, all equal, averages of 1.6666666666666667 and 0.00001, the ends 1000000000 and -1000000000
guessing-gamePro12no guesses, right on the first try, never right, guesses after the right one, 9 and 1000 against 100, 100000 guesses
till-commandsPro14close alone, an empty till, total before any sale, a total below 0, sales and closed as unknown words, commands after close, 100000 commands
count-primesPro13n = 1, 2, 3 and 4, 25 and 49, 97, 1000000, 14999981 and 15000000
first-pair-sumPro15n = 2 with and without a pair, a number that would pair with itself, the pair at the very end, a later i with a smaller j, n = 5000 with no pair

Try the small edges on the Playground. Its stdin box takes at most 10000 characters, so it cannot hold the largest tests. That limit belongs to the box, not to the judge. A test you write yourself with one edge in it says more than a big one anyway.

The forms these ten problems need

const n = nextInt();                       read a count first
for (let i = 0; i < n; i++) { ... }        the body runs n times
for (let i = 1; i <= n; i++) { ... }       i takes 1, 2, ... n, n included
let x = nextInt();                         read before a sentinel loop...
while (x !== 0) { ... x = nextInt(); }     ...and again at the end of each pass
let t = next();                            undefined once the input ends
while (t !== undefined) { ... t = next(); }
if (a) { ... } else if (b) { ... } else { ... }   the first true test wins
switch (v) { case 1: ... break; default: ... }    v === each case, top down
case 6: case 7: ...                        two cases share one body
break;                                     leave the nearest loop or switch
outer: for (...) { for (...) { break outer; } }   leave both loops
i % 3 === 0                                i is a multiple of 3
  • Every starter below is the fixed starter of the track. Keep its lines, and write your code where the comment says.
  • Push one line of output per answer. Words are printed exactly as the statement writes them, in the same case.
  • A number pushed to out prints the way String() prints it, so you never format one by hand.
Example 1: a counted loop that stops early

Zara logs her phone's battery level n times a day. She wants the first reading below 20, and she wants to stop reading once she has 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();
let checked = 0;
let found = false;

for (let i = 1; i <= n; i++) {
  const level = nextInt();
  checked++;
  if (level < 20) {
    out.push("first low " + level + " at reading " + i);
    found = true;
    break;
  }
}
if (!found) {
  out.push("never low");
}
out.push("readings checked " + checked);

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

first low 19 at reading 4
readings checked 4

That output is for the input 6 and 85 60 41 19 12 50. The loop was ready for six passes, and break ended it after four. The flag found tells the code after the loop which way it ended, so never low prints only when no reading was low.

Run in Compiler
Example 2: a switch inside a loop that reads until the input ends

Amara's driving simulator reads traffic-light colours, one per token, until the input ends. Two spellings mean the same light, so their cases share one body.

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 lights = 0;
let colour = next();

while (colour !== undefined) {
  lights++;
  switch (colour) {
    case "green":
      out.push("go");
      break;
    case "amber":
    case "yellow":
      out.push("slow down");
      break;
    case "red":
      out.push("stop");
      break;
    default:
      out.push("unknown " + colour);
  }
  colour = next();
}
out.push("lights " + lights);

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

go
slow down
stop
unknown blue
slow down
lights 5

That output is for the input green amber red blue yellow. amber and yellow reach the same body, because case "amber": has no body of its own and falls through. Each break here leaves the switch only, and the while loop goes on until next() gives undefined.

Run in Compiler
Example 3: two nested loops and one labelled break

Kenji's cinema app finds the first free seat, row by row. The input is the number of rows and seats per row, then a 1 for every taken seat and a 0 for every free 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 = [];

const rows = nextInt();
const seats = nextInt();
let checked = 0;
let answer = "no free seat";

search: for (let r = 1; r <= rows; r++) {
  for (let s = 1; s <= seats; s++) {
    const taken = nextInt();
    checked++;
    if (taken === 0) {
      answer = "free seat: row " + r + ", seat " + s;
      break search;
    }
  }
}
out.push(answer);
out.push("seats checked " + checked);

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

free seat: row 2, seat 3
seats checked 7

That output is for the input 3 4, then the rows 1 1 1 1, 1 1 0 1 and 0 1 1 1. break search; leaves both loops at seat 7, so the free seat in row 3 is never looked at. A plain break would leave only the inner loop, and row 3 would be searched as well.

Run in Compiler

Where this is used

  • HTTP/1.1 chunked transfer encoding. A server that streams a reply sends it in chunks, each with its size first, and a chunk of size 0 ends the body. That 0 is a sentinel, exactly the shape of sum-until-zero.
  • Node's readline module. It reads a stream line by line and emits a close event when the input ends. Command-line tools written in Node use that event as their "until the input ends" test.
  • The Unix head tool. head -n 10 prints the first ten lines of its input and stops, however long the input is. It is a counted loop with an early exit.
  • Array.prototype.find. The ECMAScript specification defines it as a loop that returns the first element passing the test, and looks at nothing after it. Module 7 uses it; inside, it is the early exit of guessing-game.

Common mistakes

1. Reading one token too many.

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();
let sum = 0;
for (let i = 0; i <= n; i++) {
  sum += nextInt();
}
out.push(sum);

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

NaN

That is the output for the input 3 and 4 5 6. With i = 0 and i <= n the loop runs four times, and the fourth nextInt() gives NaN. No error appears, so only the judge's Wrong Answer tells you. You will make this mistake because <= n looks right when you count from 1. Count from 0 with < n, or from 1 with <= n.

2. A break inside a switch, meant to end the loop.

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 word = next();
while (word !== undefined) {
  switch (word) {
    case "stop":
      break;
    default:
      out.push(word);
  }
  word = next();
}

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

ready
set
go

That is the input ready set stop go, and go should never print. The break left the switch, the nearest thing it could leave, and the loop read on. You will make this mistake because break means "stop" in both places. End the loop with a flag in its test, or put a label on the loop and write break with that label.

3. A sentinel counted as data.

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 total = 0;
let age = 0;
do {
  age = nextInt();
  count++;
  total += age;
} while (age !== -1);
out.push(count + " ages, total " + total);

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

3 ages, total 39

That is the input 20 20 -1, where -1 marks the end, so the answer is 2 ages and a total of 40. A do...while loop runs its body before its test, so the -1 was counted and added before the test saw it. Read once before a while loop, and read again as the last line of each pass.

4. A running minimum that starts at 0.

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();
let coldest = 0;
for (let i = 0; i < n; i++) {
  const t = nextInt();
  if (t < coldest) {
    coldest = t;
  }
}
out.push("coldest " + coldest);

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

coldest 0

That is the input 3 and 5 8 3. No reading was 0, yet 0 won, because it was never beaten. The program is right on any input with a value below 0, which is why a sample with a negative number hides it. Start a running minimum or maximum from the first value read.

Brain teaser

Zara plays guessing-game with a plan. She always guesses the middle of the numbers still possible, and after each higher or lower she throws away the half that cannot hold the secret. The secret can be anything from 1 to 1000000000.

What is the largest number of guesses Zara can ever need? Bob says it could take a million.

Each wrong guess leaves at most half of the numbers that were still possible. How many halvings take 1000000000 numbers down to one?

Problem 1: steps-goalEasyFree

Zara's step counter records how many steps she walks each day, and her goal is g steps a day. For every day, she wants to know whether she met the goal, and at the end, on how many days she did. Read the input with the starter's nextInt().

Input. The first line holds n and the goal g. The second line holds n whole numbers: the steps of each day, in order.

Output. n + 1 lines. For each day in order, print met when its steps are at least g, and otherwise short. The last line holds the number of days met.

Constraints. 1 <= n <= 100000. 0 <= g <= 100000. 0 <= steps <= 100000.

Sample. Input 5 8000 and 7500 8000 12030 0 9100 gives short, met, met, short, met and 3 on six 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"));
Run in Compiler

Hint 1

What does "at least" mean for a day with exactly g steps? Which comparison operator says it?

Hint 2

Read n and g first. Then loop n times: read one day, push one word, and add 1 to a counter on the days that count. Push the counter once, after the loop.

Solution

A for loop that runs n times reads each day with nextInt() and compares it with >=, the operator for "at least". A met day pushes met and adds 1 to a counter that starts at 0, and the counter is pushed after the loop. With g = 0 every day is met, a day of 0 steps included.

> instead of >= calls the sample's 8000-step day short, and the sample catches it. Reading the steps with next() compares text, and "12030" >= "8000" is false because "1" comes before "8". A test such as steps && steps >= g calls a 0-step day short even when the goal is 0, and a hidden test tries exactly that.

Problem 2: letter-gradeEasyFree

Maria marks her class's tests out of 100 and turns each mark into a letter grade. A few marks were typed wrong, such as 101 or -1, and she wants those flagged instead of graded. Read the input with the starter's nextInt().

Input. The first line holds n. The second line holds n whole numbers, the marks.

Output. n lines, one per mark, in the input order. Print A for 90 to 100, B for 80 to 89 and C for 70 to 79. Print D for 60 to 69 and F for 0 to 59. Print invalid for a mark below 0 or above 100.

Constraints. 1 <= n <= 100000. -1000 <= mark <= 1000.

Sample. Input 7 and 95 89 70 65 59 101 -1 gives A, B, C, D, F, invalid and invalid on seven 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"));
Run in Compiler

Hint 1

The test that runs first decides everything after it. What happens to 95 if the first test asks whether the mark is at least 60?

Hint 2

Rule out the invalid marks first. Then test the bands from the top down, A first, so each later test needs only the lower end of its band.

Solution

An if and else if chain stops at the first true condition. Once the marks below 0 and above 100 are out, mark >= 90 can only mean 90 to 100. The next test, mark >= 80, can only mean 80 to 89, because 90 and up never reach it. Four such tests and a final else for F cover every valid mark.

> instead of >= moves every boundary mark down a letter, so 70 becomes D and the sample fails. mark >= 100 as the invalid test turns a perfect 100 into invalid, and mark <= 0 does the same to 0; the hidden tests try both ends. A chain written from the bottom up, with the 60 test first, prints D for every mark from 60 to 100.

Problem 3: day-nameEasyPro

David's calendar app stores a day as a number: 1 is Monday and 7 is Sunday. He wants each day's name and whether it falls on the weekend, and any number outside 1 to 7 flagged as a bug. Read the input with the starter's nextInt().

Input. The first line holds n. The second line holds n whole numbers.

Output. n lines, one per number, in the input order: the day's English name, a space, and weekday for 1 to 5 or weekend for 6 and 7. Print invalid for any other number. The names are Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday.

Constraints. 1 <= n <= 100000. -1000 <= each number <= 1000.

Sample. Input 4 and 1 6 7 9 gives Monday weekday, Saturday weekend, Sunday weekend and invalid 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"));
Run in Compiler

Hint 1

Two of the seven days share their second word. Can two cases of a switch share one body?

Hint 2

Switch on the number. Each weekday case sets its name and ends with a break. The two weekend cases sit one above the other with one body, and the default case catches every number that is not a day.

Problem 4: sum-until-zeroEasyPro

Kenji's shop scanner sends the day's price changes as a stream of numbers, and a 0 marks the end of the list. The scanner keeps sending noise after the 0, and Kenji must ignore it. Read the input with the starter's nextInt().

Input. Whole numbers separated by spaces or line breaks. The list ends at the first 0, which is not part of it, and anything after that 0 is ignored. There is always at least one 0.

Output. Two lines: how many numbers came before the first 0, and their sum.

Constraints. At most 100000 numbers come before the first 0. Each number is between -1000000 and 1000000.

Sample. Input 5 -2 7 0 4 4 gives 3 and 10 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"));
Run in Compiler

Hint 1

You do not know how many numbers will come. What tells you the list is over, and is that number part of the list?

Hint 2

Read one number before the loop. Let the loop run while that number is not the end marker. In each pass, count it, add it, and read the next number as the last step.

Problem 5: fizzbuzzEasyFree

Alice is preparing for her first interview, and FizzBuzz is the warm-up question there. She counts from 1 to n, but replaces some numbers with words. Read n with the starter's nextInt().

Input. One line with n.

Output. n lines, one for each i from 1 to n. Print FizzBuzz when i is a multiple of both 3 and 5. Print Fizz when it is a multiple of 3 only, and Buzz when it is a multiple of 5 only. Otherwise print the number 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 fifteen 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"));
Run in Compiler

Hint 1

15 is a multiple of 3. In an if and else if chain, which test does 15 meet first if the test for 3 comes first?

Hint 2

Count i from 1 to n, both ends included. Test for a multiple of 15 first, then of 3, then of 5, and push i itself when none of the three is true.

Solution

i % 3 === 0 is true when 3 divides i with nothing left over. A number divisible by both 3 and 5 is divisible by 15. So the 15 test must come first, or the 3 test catches 15 and pushes Fizz. The loop starts at 1 and includes n, so it runs exactly n times. Pushing the number i itself works, because out.join turns it into text.

With the 15 test last, line 15 of the sample prints Fizz. A loop with i < n stops one line short, and one that starts at 0 prints FizzBuzz first, because 0 is a multiple of every number. The largest hidden test asks for 100000 lines, which the starter's single console.log prints in about a tenth of a second locally.

Problem 6: min-max-averageMediumPro

Amara's program reads a sensor's readings once, in a single pass. She wants four facts about them: how many there are, the smallest, the largest and the average. Read the input with the starter's nextInt().

Input. The first line holds n. The second line holds n whole numbers.

Output. Four lines. Line 1 is count, a space and n. Line 2 is min, a space and the smallest number, and line 3 is max, a space and the largest. Line 4 is average, a space and the sum divided by n, as JavaScript prints the number (what String() gives).

Constraints. 1 <= n <= 100000. Each number is between -1000000000 and 1000000000, so the sum is an exact whole number.

Sample. Input 5 and 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"));
Run in Compiler

Hint 1

If every number is positive, what does a running minimum that starts at 0 report? And a running maximum that starts at 0, if every number is negative?

Hint 2

Let the first number be the minimum, the maximum and the start of the sum. Then loop over the other n - 1 numbers and update all three in the same pass.

Problem 7: guessing-gameMediumPro

Bob plays a number guessing game against a program that knows a secret number. His guesses arrive one after another, until he hits the secret or runs out, and after each wrong guess the program says higher or lower. Read the input with the starter's nextInt() and next().

Input. The first number is the secret s. Then come the guesses, separated by spaces or line breaks, until the input ends. There may be no guesses at all.

Output. One line per guess, in order. When the guess is the secret, print correct in k, where k counts the guesses read, this one included, and stop: ignore any guesses after it. When the secret is higher than the guess, print higher; when it is lower, print lower. If the input ends without a right guess, print not found after k, where k is the number of guesses read, possibly 0.

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

Sample. Input 50 and 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"));
Run in Compiler

Hint 1

How does your program know the guesses are over? What does next() return once the tokens run out?

Hint 2

Read the secret, then read guesses in a while loop that runs until the token is undefined. Count every guess as you read it. On the right guess, push the line and leave the loop at once, and remember that you found it.

Problem 8: till-commandsMediumPro

Kenji's shop till reads commands until the input ends. It keeps a running total, which starts at 0 and may go below 0. Read each command word with the starter's next() and each amount with nextInt().

Input. Commands separated by spaces or line breaks, until the input ends. sale x adds x to the total, and refund x subtracts x. total prints the total, and close prints the total and ends the run. Any other word is an unknown command, with no amount after it.

Output. For total, print total, a space and the total. For close, print closed, a space and the total; every command after it is ignored. For an unknown word, print unknown, a space and that word. If the input ends without close, print no close as the last line.

Constraints. At most 100000 commands. Every amount is a whole number from 1 to 1000000. A command word is lower-case letters only.

Sample. Input sale 250 sale 100 refund 50 total tip close sale 5 gives total 300, unknown tip and closed 300 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"));
Run in Compiler

Hint 1

Which commands carry an amount after them, and which do not? After an unknown word, what is the next token?

Hint 2

Read one word per pass until the input ends, and switch on it. Only the sale and refund cases read an amount. A break inside a switch leaves only the switch, so close needs another way to end the loop.

Problem 9: count-primesHardPro

Maria asks how many primes there are up to fifteen million, and Kenji says the computer can simply count them. A prime is a whole number greater than 1 whose only divisors are 1 and itself. Read n with the starter's nextInt().

Input. One line with n.

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

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"));
Run in Compiler

Hint 1

Testing every number up to 15000000 for a divisor gives the right answer. How long does it take, and how long does the judge wait?

Hint 2

Turn the question around. Instead of asking whether each number has a divisor, let each prime cross out its own multiples. Keep one true or false flag per number from 0 to n, and count the flags still true at the end.

Problem 10: first-pair-sumHardPro

In a mock interview, Alice gets a list of numbers and a target. She must find the first pair of positions whose two numbers add up to the target. Read the input with the starter's nextInt().

Input. The first line holds n and the target t. The second line holds n whole numbers, a1 to an.

Output. One line. Print the first pair of positions i < j, counted from 1, with ai + aj = t, as i j. "First" means the smallest i, and for that i, the smallest j. Print none when no such pair exists.

Constraints. 2 <= n <= 5000. -1000000000 <= ai <= 1000000000. -2000000000 <= t <= 2000000000.

Sample. Input 6 10 and 3 8 5 7 2 5 gives 1 4: 3 + 7 is 10, and the pairs 8 + 2 and 5 + 5 come later.

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"));
Run in Compiler

Hint 1

For position i, which positions j can pair with it? Can j be i itself, or a position before i?

Hint 2

Keep the numbers, then use two nested loops: i over every position, and j over the positions after i only. Check the pairs in that order, and leave both loops at the first match.

Common doubts

  • My program prints NaN as its last line. Where does it come from?

    Your loop read one token more than the input has. next() then gives undefined, Number(undefined) is NaN, and NaN spoils any sum it touches. Check the loop's test: from 0, i < n runs n times, and i <= n runs n + 1 times.

  • The Playground ran my count-primes fine. Why does the judge say Time Limit Exceeded?

    The Playground stops a run after 10 seconds, and the judge gives a JavaScript program 2 seconds per test. At n = 15000000, trial division by the primes found so far took about 4 seconds in two Playground runs. It finishes there, and it is far too slow for the judge. A program that passes the small tests and fails only the largest is usually too slow, not wrong.

  • Can I use for...of, forEach or Math.min instead of the loops shown here?

    The judge reads only your output, so any correct program passes. for...of works over an array you built yourself. forEach has no way to stop early, so it does not suit guessing-game or first-pair-sum; lesson 04 shows why. Module 7 teaches the array methods properly.

  • Why do some statements say "spaces or line breaks"?

    The starter splits the whole input into tokens, so a line break and a space mean the same thing to it. sum-until-zero, guessing-game and till-commands say so, and their hidden tests use both. A program that reads the first line only misses every number on the next one.

  • My program passes the sample. Why does a hidden test fail?

    The sample is one small case, chosen to explain the statement. The hidden tests add n = 1, values exactly on a boundary, an input with nothing to read and the largest sizes. The table of edges above names them; run the small ones on the Playground before you submit.

Key takeaways

  • Read with a count when the input gives n, with a sentinel when a value ends the list, and until next() gives undefined when nothing does.
  • Write the comparison the statement says: "at least" is >=, and a band such as 80 to 89 includes both of its ends.
  • In an else if chain or a switch, order decides the answer: test 15 before 3, and end every case with break unless it shares a body on purpose.
  • Stop as soon as the answer is known: break leaves one loop, a labelled break leaves two, and a break inside a switch leaves only the switch.
  • Start a running minimum or maximum from the first value, and pick an algorithm that fits the judge's 2 seconds, such as the sieve.
  • Go deeper: CP and Interview Pack, nested loops, early exit and the bug gallery (Pro).

Next come the cheat sheet, which puts the whole module on one page, and the module test: ten questions and two of these problems, fizzbuzz and min-max-average. After them, Module 5 opens functions.

End of lesson 7

Get every problem accepted, and the lesson is done.

0 of 3 free problems accepted

Next: Cheat Sheet: if, switch and Loops on One Page

Next lesson