05. Loops — Homework Solutions

The answer .cpp files are in exercises/05/homework/solutions/.

Open this page after trying on your own. Compare your line of thinking with the How to think about it section, not the code line by line: two pieces of code with different shapes can both be correct, and what is worth copying is how to get there. The Test section of each problem contains input and output that have already been checked — run your own answer with that input before considering yourself done.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/05/homework/solutions/01-jumlah-n.cpp
./jawab

Problem 1 — Sum from 1 to N

Problem. Read n up to 1,000,000, print the sum from 1 to n.

How to think about it. An ordinary accumulation pattern. What is being tested here is the choice of type: for n = 1,000,000, the result is 500,000,500,000 — about 5 × 10¹¹, far past the limit of int. The accumulator must be long long.

Walkthrough.

int n;
cin >> n;

long long total = 0;
for (int i = 1; i <= n; i++) total += i;

cout << total << "\n";

The formula n × (n + 1) / 2 gives the same answer without a loop:

long long total = (long long)n * (n + 1) / 2;

The (long long)n form matters: without it, n * (n + 1) is computed as int and overflows before it can be stored.

Tests.

The third row is a data type check: with an int accumulator, the program prints 1784293664 — a number that looks nothing like the correct answer, and comes with no error message at all.

Common mistakes.

• Using int total. The result is a negative number with no error message.
• Using the formula but forgetting the cast, so the result is still wrong.

Problem 2 — Digit sum

Problem. Sum the digits of a number up to 10¹⁸.

How to think about it. Take the last digit with % 10, add it to the accumulator, drop that digit with / 10, repeat while the number is still greater than zero. Because the limit is 10¹⁸, the number read must be long long; the sum accumulator may be int because its maximum is only 19 × 9 = 171.

Walkthrough.

long long n;
cin >> n;

int jumlah = 0;
while (n > 0) {
    jumlah += n % 10;
    n /= 10;
}

cout << jumlah << "\n";

Tests.

The last row tests two things at once: an 18-digit number only fits in long long, and its digit sum (18 × 9 = 162) confirms that all the digits were read, not just some.

Common mistakes.

• Reading into an int for 10¹⁸ input. cin will fail and n holds an unpredictable value.
• Writing while (n >= 0), which never stops because 0 / 10 is still 0.

Problem 3 — Multiplication table

Problem. Print an n × n table, numbers separated by spaces, with no space at the end of the row.

How to think about it. Two nested loops: the outer one handles rows, the inner one handles columns. The tricky part is the spaces. If you write cout << i * j << " ", every row ends with an extra space. Some judges forgive it, some do not — get used to the safe way: print the space before the number, except for the first number.

Walkthrough.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (j > 1) cout << " ";
        cout << i * j;
    }
    cout << "\n";
}

Tests. Input 3 produces:

1 2 3
2 4 6
3 6 9

Check that there is no space at the end of a row. The easiest way: print the space before the number except for the first column, or print the number followed by a space except for the last column.

Common mistakes.

• Putting cout << "\n" inside the inner loop, so every number lands on its own line.
• Using endl inside a large loop. For output of thousands of lines, "\n" is much faster.

Problem 4 — Number triangle

Problem. Print a triangle pattern containing the numbers 1 up to the row number.

How to think about it. Look at the relationship between the row number and its contents: row b contains the numbers 1 to b. So the bound of the inner loop is the outer loop's variable. This is the same pattern as the star triangle in the chapter, only what is printed changes from * to the column number.

Walkthrough.

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

Tests. Input 4 produces:

1
12
123
1234

Note the relationship between a row and its contents: row i contains the numbers 1 to i. That means the bound of the inner loop depends on the outer loop — the same shape as the star triangle in Chapter 05.

Common mistakes.

• Writing kolom <= n in the inner loop, so every row has the same length.
• Printing baris instead of kolom, so the output is 1 / 22 / 333.

Challenge — Prime number test

Problem. Determine whether n up to 10¹² is prime or not.

How to think about it. Checking every number from 2 to n − 1 means 10¹² steps — it would take hours. The key: if n = a × b with a ≤ b, then a ≤ √n. This means that if there is no factor up to the square root of n, there will be no factor at all. The number of steps drops to 10⁶, finished in a fraction of a second.

Write the condition as i * i <= n, not i <= sqrt(n): sqrt works with double and can be off by one for large numbers.

Do not forget two edge cases: n = 0 and n = 1 are not prime, while n = 2 is prime.

Walkthrough.

long long n;
cin >> n;

if (n < 2) {
    cout << "BUKAN\n";
    return 0;
}

bool prima = true;
for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        prima = false;
        break;
    }
}

cout << (prima ? "PRIMA" : "BUKAN") << "\n";

Tests.

The first row is the edge case most often missed: 1 is not a prime number, but the loop i * i <= n never runs for n = 1, so the program answers PRIMA unless it is given a special check. The last row tests speed: with the square root approach it takes only about 31,623 iterations, while checking up to n - 1 requires almost a billion iterations.

Common mistakes.

• Writing int i in the loop. For n close to 10¹², i * i overflows as an int.
• Forgetting break. The program is still correct, but it does the rest of the loop for nothing.
• Answering PRIMA for n = 1, because the loop never runs and prima stays true.

OSN-style exercises — walkthrough

The answer files are in exercises/05/osn/solutions/.

Problem 1 — Collatz Sequence

How to think about it. The number of steps is not known before running, so the form is while, not for. The stopping condition is taken directly from the problem statement: "as long as the number is not yet equal to 1".

The part that decides whether the answer is right or wrong is not the loop but the data type. The constraint N ≤ 10⁶ tempts you to use int, but the values that appear in the middle of the sequence are much larger than N.

Walkthrough.

long long n;
cin >> n;

long long langkah = 0;
while (n != 1) {
    if (n % 2 == 0) n /= 2;
    else n = 3 * n + 1;
    langkah++;
}

cout << langkah << "\n";

Tests.

The last row is a type check. Starting from 704,511, the sequence reaches 56,991,483,520 — the largest value that appears for any N up to 10⁶. With an int accumulator, that value overflows, the sequence veers onto the wrong path, and the program prints 211 instead of 242. There is no error message at all.

Common mistakes.

• Using int. The program still runs and still prints a number.
• Counting the step before the rule is applied, so N = 1 gives 1, not 0.
• Writing while (n > 1) and then adding a branch for even n only. For this problem while (n > 1) is also correct, but only because the sequence is guaranteed to come down to 1; the safer habit is to copy the stopping condition from the problem statement as is.

Problem 2 — Palindrome Number

How to think about it. Reversing a number uses the same % 10 and / 10 pair as the Processing digits section of Chapter 05, but in the opposite direction: each digit taken from the back is pushed onto the front of the accumulator with balik = balik * 10 + digit.

One trap: the loop consumes n, so the original value must be copied before the loop starts. Otherwise, at the end there is nothing left to compare.

The number of iterations is the number of digits — at most 19 for these constraints — not N times.

Walkthrough.

long long n;
cin >> n;

long long asli = n;
long long balik = 0;
while (n > 0) {
    balik = balik * 10 + n % 10;
    n /= 10;
}

if (balik == asli) cout << "YA\n";
else cout << "TIDAK\n";

Tests.

The 10 row deserves attention: its reverse is 01, which as a number has the value 1, so the answer is TIDAK. This is correct — and it is also the reason storing the digits as text is not needed.

Common mistakes.

• Forgetting to copy n into asli ("original"), so at the end n is already 0.
• Using int, so a number at the upper bound cannot be read at all.
• Writing balik = balik + n % 10 * 10. The order is wrong: the old accumulator must be shifted one digit to the left first.

Problem 3 — Number of Factors

How to think about it. The most direct way is to check every i from 1 to N and count those that divide evenly. For N ≤ 100,000 and T ≤ 50, that is about 5 × 10⁶ checks — still fits.

But there is a much better way, and it is worth getting used to now: factors always come in pairs. If i divides N evenly, then so does N / i. One of the pair is certainly no larger than the square root of N, so it is enough to check i up to i × i ≤ N and count two factors at once. The exception is square numbers, where i and N / i have the same value and must be counted only once.

Walkthrough.

int t;
cin >> t;

for (int kasus = 0; kasus < t; kasus++) {
    int n;
    cin >> n;

    int banyak = 0;
    for (int i = 1; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            banyak++;                      // factor i
            if (i != n / i) banyak++;      // its pair n/i
        }
    }

    cout << banyak << "\n";
}

Note that banyak is reset to zero inside the test case loop. This is the most common mistake in multi-case problems: an accumulator declared outside carries leftover counts from the previous case.

Tests.

Also test square numbers such as 36, whose answer is 9: if the i != n / i check is removed, the number 6 is counted twice and the answer becomes 10.

Common mistakes.

• Putting int banyak = 0; outside the test case loop.
• Forgetting i != n / i, so every square number gets one extra factor.
• Starting the loop from i = 0, which immediately causes a division by zero and a Runtime Error.

If you are still stuck

• The loop runs one time too many or too few → Chapter 05, the iterations table.
• The accumulator has a strange value → Chapter 05, the initial value table in the The accumulation pattern section.
• The program hangs → Chapter 05, the section When a loop will not stop.

Before moving on to Chapter 06, make sure you can write from memory: the pattern for summing n numbers, the pattern for finding the largest value, and the pattern for processing digits with % 10 and / 10.