05. Loops

Computers excel at work that is repeated thousands of times without getting bored. Loops are the tool for telling them to do that — and almost every OSN problem needs them.

for

The for form is used when the number of repetitions is already known:

for (int i = 1; i <= 5; i++) {
    cout << i << " ";
}
cout << "\n";

1 2 3 4 5

Three parts inside the parentheses, separated by semicolons:

The order of execution is not simply left to right; it goes like this: the initialization runs once, then the condition is checked, then the body runs, then the update, then the condition is checked again, and so on. Trace the example above:

Note two things that often surprise beginners: the condition is checked before the body runs (so the body may never run at all), and after the loop finishes, the value of i has already gone past its bound.

The variable i created inside for (int i = ...) only lives for the duration of that loop. Afterwards it no longer exists, and using it produces 'i' was not declared in this scope.

Commonly used variations:

for (int i = 0; i < n; i++)        // 0 to n-1, most common for arrays
for (int i = n; i >= 1; i--)       // backwards
for (int i = 0; i < n; i += 2)     // step by two

The number of iterations can be computed without running the program, and this is a habit to build now because Chapter 10 uses it constantly:

The third row is the most common off-by-one error: changing < to <= adds one iteration, and on an array that extra iteration touches a slot that does not exist.

while

while is used when the number of repetitions is not known in advance, only the stopping condition is known:

int n = 1234;
int banyak_digit = 0;

while (n > 0) {
    n /= 10;
    banyak_digit++;
}
cout << banyak_digit << "\n";   // 4

Tracing the example above for n = 1234:

Choosing for or while

Both are equally powerful — anything that can be written with for can be written with while, and vice versa. Pick the one that makes the intent read most clearly.

do ... while

The same as while, but the body runs at least once because the condition is checked at the end:

int pilihan;
do {
    cin >> pilihan;
} while (pilihan < 1 || pilihan > 3);

This form is rarely used for online judge problems, but it is useful for interactive programs.

break and continue

• break exits the loop immediately.
• continue jumps to the next iteration.

for (int i = 1; i <= 100; i++) {
    if (i % 3 != 0) continue;   // skip anything that is not a multiple of 3
    if (i > 20) break;          // stop as soon as we pass 20
    cout << i << " ";
}

3 6 9 12 15 18

The accumulation pattern

The most common pattern in this entire book: set up an accumulator before the loop, change its contents in every iteration, use the result after the loop.

long long total = 0;            // accumulator
for (int i = 1; i <= n; i++) {
    total += i;                 // changed every iteration
}
cout << total << "\n";          // used afterwards

Those three parts — set up, change, use — are always there. The part most often gotten wrong is "set up", because the initial value differs for each kind of accumulation:

An initial value of 0 for a product makes the answer always zero; an initial value of 0 for "largest" makes the answer wrong when all the data is negative. Both are classic mistakes that pass the sample cases in the problem and are only caught during judging.

Variations whose shape you should memorize:

// count how many satisfy a condition
int banyak = 0;
for (int i = 1; i <= n; i++) if (i % 7 == 0) banyak++;

// find the largest
int besar = -1000000000;
for (int i = 0; i < n; i++) { cin >> x; if (x > besar) besar = x; }

// running product (factorial)
long long hasil = 1;
for (int i = 2; i <= n; i++) hasil *= i;

Processing digits

Combining % 10 and / 10 from Chapter 03 inside a while gives a way to read a number digit by digit, from the back:

long long n = 4071;
int jumlah = 0;

while (n > 0) {
    int digit = n % 10;   // take the last digit
    jumlah += digit;
    n /= 10;              // drop the last digit
}
cout << jumlah << "\n";   // 12

Nested loops

A loop may sit inside another loop. The inner one runs completely for every iteration of the outer one.

for (int baris = 1; baris <= 4; baris++) {
    for (int kolom = 1; kolom <= baris; kolom++) {
        cout << "*";
    }
    cout << "\n";
}

*
**
***
****

How to read it: the outer loop determines how many rows, the inner loop determines the contents of one row. For the example above:

In total 1 + 2 + 3 + 4 = 10 stars. Also note where cout << "\n" sits: it is inside the outer loop but outside the inner loop. Moving it one level in puts every star on its own line; moving it out puts everything on one long line.

The amount of work multiplies too: two nested loops that each go up to n do about n² steps. For n = 1000 that is a million steps (fast), for n = 100000 that is ten billion (far too slow). Chapter 10 covers how to estimate this before writing code.

The multiple test case pattern

Many contest problems give the number of test cases on the first line. The standard form:

int t;
cin >> t;
while (t--) {
    int a, b;
    cin >> a >> b;
    cout << a + b << "\n";
}

t-- gives the current value of t to while, then decrements it by one. When t reaches 0, the loop stops.

When a loop will not stop

A program that hangs without printing anything almost always means one of three things:

1. The value being checked never changes. Check whether there is a line inside the loop that actually changes it.
2. The change moves away from the stopping condition. For example i-- in a loop that waits for i to reach n.
3. The program is waiting for input. Not an infinite loop, but a cin >> waiting for a number you never typed.

Stop a hanging program with Ctrl + C. To see what is actually happening, temporarily insert cerr << i << " " << n << "\n"; inside the loop — cerr is used, not cout, so it does not pollute the judged output (Chapter 10).

Homework

1
12
123
1234

Most common mistakes

OSN tips

The multiple test case pattern must be automatic. Some OSN problems wrap one small problem in T test cases. The form is always the same, and you should have it memorized:

int t;
cin >> t;
while (t--) {
    // read one case, print one answer
}

Two mistakes that often appear in this pattern: an accumulator variable that is not reset to zero at the start of each case, and answers that are collected first and printed at the end when the problem asks for one line per case.

Estimate the number of steps before writing code. The rough rule used throughout this book: the judge machine completes about 10⁸ simple operations per second. From that, the constraints in the problem directly tell you the shape of solution that fits:

A constraint of 10¹⁸ is a clear signal: what is wanted is a formula or a loop over its digits, not over its value.

Intermediate values can be much larger than the input. A problem that states N ≤ 10⁶ does not guarantee that every number in your program stays small. The Collatz sequence below is an example: starting from 704,511, the sequence reaches 56,991,483,520 — more than twenty times past int.

A loop that does not stop is judged Time Limit Exceeded, not an error. If your answer is correct on your own computer but gets TLE on all test files, suspect a stopping condition that is never reached — for example while (n != 1) for an n that can be 0.

Output with many lines is better collected. For problems that print hundreds of thousands of lines, printing with endl in every iteration makes the program many times slower. Use "\n".

Summary

• for is used when the number of iterations is known, while when only the stopping condition is known.
• The three parts of for: initialization (once), condition (before each iteration), update (after each iteration).
• for (int i = 0; i < n; i++) runs n times and matches array indices; changing < to <= adds one iteration.
• Accumulation pattern: set up the accumulator, change it every iteration, use it afterwards. The initial value differs for a sum, a product, and a largest value.
• while (n > 0) { n % 10; n /= 10; } reads a number digit by digit from the back.
• Nested loops do about n² steps — enough for n in the thousands, not for n in the hundreds of thousands.
• Accumulators in multi-test-case problems must be reset for every case.

OSN-style exercises

All three problems below are solved with loops only — no arrays needed yet. The third problem uses the multiple test case pattern you will often encounter in OSN.

Starter code for all three is in exercises/05/osn/.

Problem 1 — Collatz Sequence

Take a positive integer N. As long as the number is not yet equal to 1, apply the following rule repeatedly:

• if the number is even, divide it by two;
• if the number is odd, multiply it by three and add one.

One application of the rule counts as one step. Compute how many steps are needed until the number becomes 1.

Input format. One line containing one integer N.

Output format. One line containing the number of steps.

Constraints. 1 ≤ N ≤ 10⁶. For every N within these constraints, the sequence is guaranteed to reach 1.

Sample input

6

Sample output

8

Explanation. The sequence is 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, which is eight steps. For N = 1, the answer is 0 because the number is already 1 from the start.

Starter code: exercises/05/osn/01-collatz.cpp

Problem 2 — Palindrome Number

A number is called a palindrome if its sequence of digits reads the same from the front as from the back. For example 12321 and 7 are palindromes, while 12345 and 10 are not.

Input format. One line containing one integer N.

Output format. One line containing YA ("yes") if N is a palindrome, or TIDAK ("no") if it is not.

Constraints. 1 ≤ N ≤ 10¹⁸. The number must not be read as text.

Sample input

12321

Sample output

YA

Explanation. The digits of 12321 read from the back are still 12321. Note the constraint 10¹⁸: a number that large does not fit in int, and a loop running N times is clearly impossible — what is repeated over is the digits, and there are at most 19 digits.

Starter code: exercises/05/osn/02-palindrom-angka.cpp

Problem 3 — Number of Factors

For each given number, count how many positive integers divide it evenly.

Input format. The first line contains one integer T, the number of test cases. Each of the next T lines contains one integer N.

Output format. T lines. Line i contains the number of positive factors of N in test case i.

Constraints.

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100,000

Sample input

3
12
1
97

Sample output

6
1
2

Explanation. The factors of 12 are 1, 2, 3, 4, 6, and 12 — six of them. The number 1 has only one factor, itself. The number 97 is a prime number, so its only factors are 1 and 97.

Starter code: exercises/05/osn/03-banyak-faktor.cpp

Confused, or already done? Open the homework solutions page.