Loops

A loop repeats a piece of code: a fixed number of times (for) or as long as a condition holds (while). You need one whenever the input has $n$ values or an action must be repeated until something happens.

Explanation

A program reads $n$ and prints the numbers from 1 to $n$. For n = 3, three lines with cout would do, but $n$ comes from the input. A while loop writes the line once and runs it as many times as needed:

int i = 1;
while (i <= n) {
    cout << i << " ";
    i++;
}

The program first checks the condition i <= n, a comparison like the one in an if. If it is true, it runs the code in braces, the body, and comes back to the check. If it is false, it goes on with the code after the loop. One run of the body is an iteration.

Fig. 1. The condition is checked before every iteration.

The body ran 3 times, but the condition was checked 4 times: the last check, with i equal to 4, ends the loop.

The for loop

A for loop puts the start int i = 1, the condition i <= n and the step i++ into one line, the loop's header:

for (int i = 1; i <= n; i++)
    cout << i << " ";

The start runs once, and then come the condition, the body, the step, the condition again, and so on, until a check is false. The variable i, which changes from one iteration to the next, is the loop variable. A variable declared in the header exists only inside the loop. To use it after the loop, declare it before the loop.

Running sum and running count

A program reads $n$, then $n$ numbers, and prints their sum. A variable sum is set to 0 before the loop, and each iteration reads one number and adds it. After each iteration, sum holds the sum of the numbers read so far. A variable like this is a running sum. It is a long long, because an int holds only up to about 2.1 \cdot 10^9.

long long sum = 0;
int x;
for (int i = 0; i < n; i++) {
    cin >> x;
    sum += x;
}
cout << sum << "\n";

This loop takes i from 0 to n − 1: still n iterations, and here only their number matters. Trace it with n = 5 and the numbers 4, −2, 7, 0, 3.

Start: i = 0 and sum = 0; no number has been read yet.

Condition: 0 < 5 is true (green), so the body runs.

Body: cin >> x reads 4, sum = 0 + 4 = 4. Step: i = 1. The blue number is the one just read into x, and red cells are the values that changed.

Condition: 1 < 5 is true.

Body: cin >> x reads −2, sum = 4 + (−2) = 2. Step: i = 2. Grey numbers, under the bracket, were added earlier.

Condition: 2 < 5 is true.

Body: cin >> x reads 7, sum = 2 + 7 = 9. Step: i = 3.

Condition: 3 < 5 is true.

Body: cin >> x reads 0, sum = 9 + 0 = 9. Step: i = 4.

Condition: 4 < 5 is true.

Body: cin >> x reads 3, sum = 9 + 3 = 12. Step: i = 5.

Condition: 5 < 5 is false (red), so the loop ends.

The program prints sum, 12.

1/13

Fig. 2. After each iteration, sum is the sum of the numbers read so far.

A running count works the same way. This loop counts how many of the numbers are greater than 4:

int cnt = 0;
for (int i = 0; i < n; i++) {
    cin >> x;
    if (x > 4)
        cnt++;
}

Nested loops

A loop inside the body of another loop runs completely in each iteration of the outer one.

Four teams play a tournament, and each pair of teams plays once. The first idea is to let both loops go from 1 to 4:

for (int i = 1; i <= 4; i++)
    for (int j = 1; j <= 4; j++)
        cout << i << "-" << j << "\n";

This prints 16 pairs: four are a team against itself, such as 2-2, and each game appears twice, as 1-3 and 3-1. The grid shows all 16: row i, column j.

Fig. 3. Only the cells with j > i are needed.

The fix is to start j at i + 1:

for (int i = 1; i <= 4; i++)
    for (int j = i + 1; j <= 4; j++)
        cout << i << "-" << j << "\n";

Now j is always greater than i, so each game appears once. The inner loop runs 3, 2, 1 and 0 times, so there are 3 + 2 + 1 + 0 = 6 games. With $n$ teams this sum is n(n-1)/2.

How many times a loop runs

Counting iterations is how the time complexity of a program is estimated.

Stopping early: break and continue

break leaves the loop at once, and the program goes on after it. This loop looks for the smallest divisor of n greater than 1 (n % d == 0 means that d divides n):

int d;
for (d = 2; d <= n; d++)
    if (n % d == 0)
        break;

For n = 91 the loop stops with d = 7 after 6 iterations, instead of going on to 91.

continue skips the rest of the current iteration and goes to the step. To add only the positive numbers of the running-sum example, skip the others:

for (int i = 0; i < n; i++) {
    cin >> x;
    if (x <= 0) continue;
    sum += x;
}

For 4, −2, 7, 0 and 3 this gives 4 + 7 + 3 = 14. In a while loop, continue goes straight to the check and skips any i++ after it.

In C++

for (int i = 0; i < n; i += 2)   // every second value: 0, 2, 4, …
for (int i = n; i >= 1; i--)     // n, n-1, …, 1

Reading until the input ends

When the input doesn't say how many numbers follow, read until it ends. As a condition, cin >> x is true when it has read a number and false when nothing is left to read:

long long sum = 0;
int x;
while (cin >> x)
    sum += x;

When you type the input by hand, end it with Ctrl+D (Ctrl+Z, then Enter, on Windows).

Counting digits

Dividing by 10 removes the last digit (integer division), so counting divisions until n is 0 counts the digits. For n = 0 the loop runs zero times, so 0, which has one digit, gets its own line:

int cnt = 0;
if (n == 0) cnt = 1;
while (n > 0) {
    n /= 10;
    cnt++;
}

Common mistakes

• One iteration too many or too few. for (int i = 1; i < n; i++) to add the numbers from 1 to n misses n: for n = 5 it gives 10, not 15. Write down the first and the last value the loop must take, then pick the header: 1 to n is i = 1; i <= n, while i = 0; i < n takes 0 to n − 1.

• Setting the running sum to 0 inside the body. The sum then restarts in every iteration, and the example prints 3 instead of 12. Set it once, before the loop.

• A semicolon after the header. for (i = 1; i <= 5; i++); has an empty body, so the line after it runs once, after the loop. With while (i <= n); the loop never ends if the first check is true.

• A loop that never stops. Without i++, the first while loop prints 1 forever, and the judge says Time limit exceeded. Every iteration must move the loop toward a false condition.

• Not resetting the loop variable of an inner while loop. To print 3 rows of 4 stars, int j = 0; before the outer loop and while (j < 4) inside it print stars only on the first row, because on the second row j is already 4. Set the inner loop variable inside the outer loop; a for loop does this in its start.

Similar techniques

Recursion also repeats work: a function calls itself. Use a loop when the work goes one action after another, and recursion when each part splits into several smaller parts.

Backtracking replaces nested loops when their number depends on the input: choosing one of two options for each of $n$ items would need $n$ nested loops.

Arrays keep the numbers a loop reads, for when they are needed again after the loop.

Practice