06. Functions — Homework Solutions

The answer .cpp files are in exercises/06/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/06/homework/solutions/01-maksimum.cpp
./jawab

Problem 1 — Maximum function

Problem. Write maksimum(a, b) and then maksimum3(a, b, c), which uses it.

How to think about it. The core of this problem: a function may call another function. Once maksimum for two numbers exists, compare its result with the third number — there is no need to rewrite the logic.

Walkthrough.

int maksimum(int a, int b) {
    return (a > b) ? a : b;
}

int maksimum3(int a, int b, int c) {
    return maksimum(maksimum(a, b), c);
}

Tests.

The value of this problem is not in the answer but in its shape: maksimum3 calls maksimum twice instead of rewriting the comparison. This pattern of "small functions used by a larger function" is what keeps long problems under control.

Common mistakes.

• Copying the comparison logic into maksimum3 instead of calling maksimum. The answer is still correct, but the learning opportunity is lost.
• Forgetting return in one of the branches. The compiler only gives a warning (with -Wall), and the return value becomes garbage.

Problem 2 — Counting prime numbers

Problem. Count the prime numbers from 1 to n.

How to think about it. Separate two jobs: one function answers "is a single number prime", and main handles the loop and the counting. The prima function is exactly the same as the Chapter 05 challenge, now wrapped so it can be reused.

The return false pattern in the middle of the loop replaces a flag variable and break — as soon as one factor is found, the answer is already certain.

Walkthrough.

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

int banyak = 0;
for (int i = 2; i <= n; i++) if (prima(i)) banyak++;
cout << banyak << "\n";

Keep its limit in mind: this approach checks every number one by one, at a cost of about n √n steps. For n = 1,000,000 it still runs in a few seconds; beyond that you need the sieve of Eratosthenes, which uses an array and is covered in Chapter 07.

Tests.

The first row is a mandatory edge case: the function prima(1) must return false. If the check is only the loop i * i <= n, that loop never runs for n = 1 and the function wrongly answers true.

Common mistakes.

• Starting the loop from 1 and then also counting 1 as prime. The guard if (n < 2) return false; prevents this.
• Counting 2 as not prime because the loop i * i <= n was written as i < n.

Problem 3 — Recursive power

Problem. pangkat(a, b) ("power") recursively.

How to think about it. The formula turns directly into code: aᵇ = a × aᵇ⁻¹, and a⁰ = 1. The base case b == 0 must be checked first; otherwise the recursion goes down to negative b and never stops.

Walkthrough.

long long pangkat(long long a, int b) {
    if (b == 0) return 1;
    return a * pangkat(a, b - 1);
}

This approach needs b calls. There is a much faster way that splits the exponent in half (a⁸ = a⁴ × a⁴), needing only about log₂ b steps. That is fast modular exponentiation in Chapter 14.

Tests.

The second row tests the base case: whatever a is, the zeroth power is 1. The third row tests the limit stated in the problem — 2⁶⁰ still fits in long long, while 2⁶⁴ no longer does.

Common mistakes.

• Writing the base case as b == 1, so pangkat(a, 0) never stops.
• Using int for the result. 2⁴⁰ is already past the limit of int.

Problem 4 — Reversing a number

Problem. Reverse the order of the digits, then check for a palindrome.

How to think about it. Building the reversed number uses one line worth memorizing:

hasil = hasil * 10 + n % 10;

Each iteration shifts the result one digit to the left (multiplied by 10), then appends the last digit of n in the ones place. Example for 4071:

Once the function exists, the palindrome check takes only one line: balik(n) == n.

Walkthrough.

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

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

Tests.

The last row shows why reversing a number is not an operation that can be undone: 1200 reversed becomes 0021, and the leading zeros disappear on their own, leaving 21. For a palindrome check this does not matter, but if a problem asks for the reversed number to be printed as is, the case of trailing zeros needs attention.

Common mistakes.

• Writing hasil = hasil + n % 10 without multiplying by 10, so what is produced is the digit sum, not the reversed number.
• Changing n in main by calling the function, then comparing with an n that has already changed. Because the parameter is a copy, n in main is safe — this is an example of why passing a copy is useful.

Challenge — Fibonacci with memory

Problem. Speed up the recursive fib by storing results that have already been computed.

How to think about it. The slow version computes fib(40) with more than 300 million calls, even though there are only 41 distinct answers. All of them are recomputed many times over.

The fix is three lines: provide an ingat array filled with -1 as the marker for "never computed", check that array at the start of the function, and fill that array before returning the result.

Walkthrough.

long long ingat[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (ingat[n] != -1) return ingat[n];
    ingat[n] = fib(n - 1) + fib(n - 2);
    return ingat[n];
}

int main() {
    for (int i = 0; i < 100; i++) ingat[i] = -1;
    ...
}

After the change, every value is computed exactly once: fib(45) finishes instantly, and even fib(90) still fits in long long (2,880,067,194,370,816,120).

Tests.

Compare the time: fib(45) without memory needs 3,672,623,805 calls, with memory only 46 states, each computed once — the answer appears instantly. The last row is the practical limit of the long long type: fib(93) already exceeds it.

Common mistakes.

• Forgetting to fill ingat with -1. A global array is filled with zeros, and zero is a valid answer for fib(0) — as a result every answer becomes zero.
• Using 0 as the "not yet computed" marker in a problem whose answer can be zero. Choose a marker that cannot possibly be an answer.
• Storing results but not checking them at the start of the function, so nothing gets faster.

OSN-style exercises — walkthrough

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

Problem 1 — Digital Root

How to think about it. This problem has two levels of loop that differ in nature: one sums the digits, the other repeats that summing until the result is a single digit. Separating the first into a function leaves the second as a single line.

The outer loop stops when n < 10. Do not use "repeat twice" or a fixed number of iterations: for N up to 10¹⁸, the digit sum is at most 19 × 9 = 171, then 1 + 7 + 1 = 9 — so at most three iterations, but writing it as a condition is much safer than counting it yourself.

Walkthrough.

long long jumlahDigit(long long n) {
    long long total = 0;
    while (n > 0) {
        total += n % 10;
        n /= 10;
    }
    return total;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        long long n;
        cin >> n;

        while (n >= 10) n = jumlahDigit(n);

        cout << n << "\n";
    }
    return 0;
}

There is a shortcut that needs no loop at all: the digital root of a positive number is always equal to 1 + (n - 1) % 9. This property comes from the fact that the digit sum and the original number always leave the same remainder when divided by 9 — the reason is covered in Chapter 14. Submit the loop version first, then compare the two for every n from 1 to 100000 as an exercise.

Tests.

Common mistakes.

• Using int for n, so the upper bound cannot be read.
• Writing while (n > 10), so an n of exactly 10 is never reduced and the answer is printed as 10 — two digits.
• Summing the digits only once, so 9875 answers 29.

Problem 2 — Tower of Hanoi

How to think about it. This is the purest recursion problem: its solution is defined in terms of the solution to the same problem at a smaller size.

To move n disks from asal (source) to tujuan (destination), the largest disk can only move once the n − 1 disks above it have moved aside to the third peg. So the order is always three steps:

1. move n − 1 disks from asal to bantu (helper), using tujuan as the helper peg;
2. move the single largest disk from asal to tujuan;
3. move n − 1 disks from bantu to tujuan, using asal as the helper peg.

The base case is n == 0: there is nothing to move.

Note that the roles of the three pegs swap in every call. That is why all three are passed as parameters rather than written as fixed values.

Walkthrough.

void pindah(int n, char asal, char bantu, char tujuan) {
    if (n == 0) return;
    pindah(n - 1, asal, tujuan, bantu);
    cout << asal << " " << tujuan << "\n";
    pindah(n - 1, bantu, asal, tujuan);
}

int main() {
    int n;
    cin >> n;

    long long banyak = (1LL << n) - 1;
    cout << banyak << "\n";

    pindah(n, 'A', 'B', 'C');
    return 0;
}

1LL << n is a quick way to write 2^n. For n ≤ 15, int would actually be enough, but the habit of using 1LL avoids overflow when the constraints are raised.

Tests. For N = 3, the output is:

7
A C
A B
C B
A C
B A
B C
A C

Check two things: the number of move lines must be exactly 2^N − 1, and the largest disk may move only once, exactly in the middle of the list. For N = 15, the output is 32,768 lines — one count line plus 32,767 moves.

echo 15 | ./hanoi | wc -l

Common mistakes.

• Swapping the order of the parameters in one of the recursive calls. The program still runs and still prints 2^N − 1 lines, but the order breaks the disk rules.
• Using endl inside the recursion. For N = 15 that is 32,767 unnecessary flushes.
• Writing the base case as if (n == 1) and then forgetting to print its move.

Problem 3 — Perfect Numbers

How to think about it. The part repeated three times — summing the factors — is lifted into a function, so main only has to compare. The way to find the factors is the same as in the Chapter 05 problem: in pairs, up to the square root of N.

Two things differ from the Chapter 05 problem. First, what is summed is the proper divisors, so N itself is not included. That is why the sum starts from total = 1 and the loop from i = 2. Second, N can reach 10⁹, so the sum of its factors can exceed the limit of int — the accumulator is long long.

The number 1 needs separate handling: it has no proper divisors at all, while the total = 1 formula would answer 1.

Walkthrough.

long long jumlahFaktorSejati(int n) {
    if (n == 1) return 0;

    long long total = 1;                    // 1 is always a proper divisor
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            total += i;
            int pasangan = n / i;
            if (pasangan != i) total += pasangan;
        }
    }
    return total;
}

Tests.

Common mistakes.

• Starting the loop from i = 1 and adding its pair, so N itself is included in the sum and every number becomes BERLEBIH.
• Forgetting to handle N = 1 separately, so the answer is SEMPURNA.
• Checking i up to N instead of up to the square root of N. For T = 100 and N = 10⁹ that is 10¹¹ iterations — far past the time limit.
• Forgetting the pasangan != i check for square numbers.

If you are still stuck

• The function is not recognized when called → Chapter 06, the section The shape of a function (write it above its caller, or declare it first).
• Changes inside the function do not carry out → Chapter 06, the table in the section Copied values and references.
• Recursion stops abruptly or never stops → Chapter 06, the section Recursion and its call stack picture.

Before moving on to Chapter 07, make sure you can explain in one sentence why the plain recursive fib is slow — the answer is half of the content of Chapter 13.