09. Flowcharts and pseudocode — Homework Solutions

Problems 1 and 2 are done on paper. The .cpp files for problem 3 through the challenge are in exercises/09/homework/solutions/.

Open this page after trying on your own. For the paper problems, write your answer first, then compare — reading someone else's answer feels clear even when you could not reproduce it yourself. The Test sections contain checked inputs and outputs for the coding problems.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/09/homework/solutions/03-dari-flowchart.cpp
./jawab

Problem 1 — Draw a flowchart

Problem. Read n, read n numbers, print how many are negative.

How to think about it. Two things must exist before the loop: a position counter (i) and an answer holder (negatif, "negative"). The first diamond handles "is there more data?", the second diamond handles "is this value negative?". The no branch of the second diamond must still be drawn — it goes straight to the step that increments i.

Answer.

Common mistakes.

• The x < 0? diamond is given only one outgoing arrow.
• The back arrow goes to read x, not to the i <= n? diamond. As a result the bound check is skipped and the loop never stops.
• Forgetting to increment i.

Problem 2 — Write pseudocode

Problem. Print all divisors of n, then their sum.

How to think about it. One loop from 1 to n, one check n divisible by i, and one accumulator. The two jobs (printing and summing) happen inside the same check, so one loop is enough.

Answer.

READ n
jumlah <- 0
FOR i FROM 1 TO n
    IF n divisible by i
        PRINT i
        jumlah <- jumlah + i
PRINT jumlah

Common mistakes.

• Writing two separate loops — one for printing, one for summing. The answer is correct, but the work is doubled.
• Starting the loop at 2, so the divisor 1 is lost.

Problem 3 — Read a flowchart, write the code

Problem. Translate the flowchart into code.

How to think about it. First recognize what the flowchart does before translating: hasil ("result") starts at 1 and is multiplied by i for every i from 1 to n. That is the factorial.

The < i <= n? > shape with a back arrow is a while; it can also be written as a for, and both are accepted.

Walkthrough.

long long hasil = 1;
int i = 1;
while (i <= n) {
    hasil = hasil * i;
    i = i + 1;
}
cout << hasil << "\n";

Tests.

The last row is an edge case that is immediately visible in the flowchart: the i <= n diamond is false from the very first check, so the loop body is skipped and hasil keeps its initial value, which is 1.

Common mistakes.

• Starting hasil at 0. Every subsequent multiplication becomes zero.
• Using int for hasil. It already overflows at 13!.

Problem 4 — Read pseudocode, predict the output

Answer.

A → 3 5. Those three lines swap the contents of two variables without a helper variable. Trace: x = 8, then y = 8 − 3 = 5, then x = 8 − 5 = 3.

B → 15. The inner loop runs i times for each i, so the total is 1 + 2 + 3 + 4 + 5. This shape appears again in Chapter 10 when counting the steps of nested loops.

C → 111. This is the Collatz sequence: an even number is halved, an odd number is multiplied by three plus one. From 27 it takes 111 steps to reach 1 — far longer than most people guess, and that is the point of running the program to check a guess.

Tests. The answer program prints all three results at once:

3 5
15
111

Fragment C is the easiest one to guess wrong: the Collatz sequence for 27 needs 111 steps, and its value climbs above 9,000 before it finally comes down to 1. Guessing it without running it is nearly impossible — and that is the lesson: for pseudocode with a conditional loop, a tracing table (Chapter 10) is more reliable than intuition.

Common mistakes.

• On A, answering 5 3 because you think the swap failed.
• On C, trying to trace 111 steps by hand. Tracing the first five steps is enough to confirm the code is correct; then let the program finish the rest.

Challenge — Fix the broken flowchart

Answer.

1. The branch from < d * d <= x? > to [ cetak x jika prima ] ("print x if prime") is the no branch and must be labeled. An unlabeled diamond makes the reader guess the direction, and on an OSN answer sheet it is marked wrong.
2. The [ d = d + 1 ] step is missing. Without it, d never changes and the inner loop spins forever.
3. The back arrow from [ cetak x jika prima ] must go to [ x = x + 1 ] and then to < x <= n? >. In the original picture it goes back to [ d = 2, prima = benar ] ("prima = true"), which repeats the check of the same number forever.

After the fixes, the correct shape is:

Walkthrough (code).

for (int x = 2; x <= n; x++) {
    bool prima = true;
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0) prima = false;
    }
    if (prima) cout << x << " ";
}
cout << "\n";

Tests.

If the flowchart is fixed correctly, the output is exactly that list. Two symptoms if one of the fixes is missed: the program hangs (the d = d + 1 step is still missing) or it prints non-prime numbers such as 4 and 9 (the back arrow still points to the wrong box).

Common mistakes.

• Putting bool prima = true; outside the outer loop. Once one composite number is found, every number after it is also treated as not prime.
• Using d < x as the inner loop bound. The answer is correct, but much slower — exactly the issue discussed in Chapter 05.

OSN-style exercises — walkthrough

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

Problem 1 — Trace the Pseudocode

How to think about it. Each iteration enters exactly one branch: if i is a multiple of 3 then a increases, otherwise b doubles. So the two variables never change together, and the trace only needs to record one change per row.

Trace for n = 10:

Answer.

a. n = 10 prints two lines: 18 then 128. b. n = 1 prints 0 then 2. The loop runs once, and 1 is not a multiple of 3, so a is never touched. c. a is the sum of all multiples of 3 from 1 to n. b is 2 raised to the count of numbers from 1 to n that are not multiples of 3, which is n − ⌊n/3⌋. d. b exceeds the int limit starting at n = 46. At n = 45 there are 30 numbers that are not multiples of 3, so b = 2³⁰ = 1,073,741,824, which still fits. At n = 46 the count is 31, so b = 2³¹ = 2,147,483,648 — one more than the largest int value.

Answer (d) is the core of the problem: even a loop this simple overflows at a very small n, because its growth is multiplicative, not additive.

Common mistakes.

• Computing b as 2 to the power n, forgetting that multiples of 3 do not double it.
• Answering (a) with one line. PRINT appears twice and both are outside the loop.
• Assuming b starts at 0. The line b <- 1 determines the whole result.

Problem 2 — Read the Flowchart

How to think about it. The decision box p * 2 <= n? with a "yes" arrow going back up is the standard shape of a while. The loop body is one line: p is doubled. As soon as p * 2 exceeds n, the flow exits and prints p.

Since p starts at 1 and is only multiplied by 2, its value is always a power of two. The loop stops exactly when doubling once more would exceed n.

Answer.

a. N = 100 prints 64. The sequence is 1, 2, 4, 8, 16, 32, 64; the next doubling, 128, already exceeds 100. b. N = 1 prints 1. The loop is never entered because 1 × 2 = 2 already exceeds 1. c. This flowchart prints the largest power of two that does not exceed N. d. N = 10¹⁸ prints 576460752303423488, which is 2⁵⁹.

Walkthrough.

long long n;
cin >> n;

long long p = 1;
while (p * 2 <= n) {
    p = p * 2;
}

cout << p << "\n";

Note that the number of iterations is only about 60 for N as large as 10¹⁸ — every iteration doubles, so the number of iterations is proportional to the logarithm of N, not to N. This is a loop shape that stays fast under any constraints.

Common mistakes.

• Writing the condition as p <= n instead of p * 2 <= n. Then p jumps one step too far, and for N = 100 it prints 128.
• Using int for p, so the multiplication overflows for large N.
• Thinking the "yes" arrow going back up means do ... while. The condition is checked before the loop body, so the translation is while.

Problem 3 — Mountain Sequence

Pseudocode.

READ n
READ a[1..n]
i <- 1
WHILE i < n AND a[i] < a[i+1]
    i <- i + 1
IF i = 1 OR i = n
    PRINT "TIDAK"
    STOP
WHILE i < n AND a[i] > a[i+1]
    i <- i + 1
IF i = n
    PRINT "YA"
ELSE
    PRINT "TIDAK"

How to think about it. The temptation is to check "where the peak is" by finding the largest value first. That approach can be correct, but it gets convoluted when the largest value appears more than once.

A cleaner way: move one pointer i forward while the sequence is still rising. When the first loop stops, i is exactly at the peak. Two checks immediately reject a wrongly shaped sequence:

• i still at the start means it never rose;
• i already at the end means it never got to fall.

After that, the same pointer continues while the sequence falls. If it finally reaches the end, the whole sequence really does rise and then fall. If it stops in the middle, there is a part that neither rises nor falls — that is, two equal numbers, or a rise again after falling.

Note that the pointer keeps moving forward and never goes back. So the whole check needs at most N steps, not N².

Walkthrough.

int i = 0;
while (i + 1 < n && a[i] < a[i + 1]) i++;

if (i == 0 || i == n - 1) {
    cout << "TIDAK\n";
    return 0;
}

while (i + 1 < n && a[i] > a[i + 1]) i++;

if (i == n - 1) cout << "YA\n";
else cout << "TIDAK\n";

This code uses indices starting at 0, so "peak at the end" is written i == n - 1, not i == n. This is the index shift discussed in the section From pseudocode to C++ — pick one way and stick with it.

Tests.

Common mistakes.

• Forgetting to check i + 1 < n inside the while condition, so a[i + 1] is read outside the array bounds on a sequence that keeps rising.
• Using <= in the rising loop, so two equal numbers are treated as still rising.
• Forgetting to check that the peak is not at the end, so an increasing sequence like 1 2 3 4 is answered YA.

If you are still stuck

• The loop in the picture never stops → Chapter 09, the table of the fixed layout of a loop.
• The pseudocode reads ambiguously → Chapter 09, the section on indentation and the example of two pieces of pseudocode that differ by one level.
• The C++ translation is off by one step → Chapter 09, the section From pseudocode to C++ and the two ways to handle the index shift.

Before moving on to Chapter 10, make sure you can read someone else's pseudocode and predict its output without running it.