16. The sum and product rules — Homework Solutions

Problem 1 is worked on paper. The .cpp files for problem 2 through the challenge are in exercises/16/homework/solutions/.

Open this page after trying on your own. For the paper problem, write down your answer first, then compare — reading someone else's answer feels clear even when you may not be able to repeat it yourself. The Tests part contains input and output that have already been checked for the coding problems.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/16/homework/solutions/02-periksa.cpp
./jawab

Problem 1 — Count on paper

a. Three-digit numbers with all even digits → 100.

The hundreds digit may not be zero, so the choices are {2, 4, 6, 8} — four ways. The tens and units digits may be zero, so {0, 2, 4, 6, 8} — five ways each. Product rule: 4 × 5 × 5 = 100.

b. Three-digit numbers with at least one digit 7 → 252.

Via the complement. There are 900 three-digit numbers in total. Those that do not contain 7 at all: the hundreds digit has 8 choices (1–9 without 7), the tens and units digits 9 each (0–9 without 7) → 8 × 9 × 9 = 648. The answer is 900 − 648 = 252.

c. From 1 to 1,000, divisible by 4 or 6 → 333.

⌊1000/4⌋ = 250, ⌊1000/6⌋ = 166, and the intersection is the multiples of LCM(4, 6) = 12: ⌊1000/12⌋ = 83. So 250 + 166 − 83 = 333.

Note that the intersection uses the LCM, not the product 4 × 6 = 24. Using 24 gives the wrong answer 375.

d. Menu packages → 36.

One food (4 ways) and one drink (3 ways) are required. The dessert has 3 states: take the first one, take the second one, or take none. So 4 × 3 × 3 = 36.

This combines both rules: "may or may not be taken" is the sum rule (2 + 1), which then goes into the product.

Problem 2 — Check with a program

How to think about it. For each part, write a loop that actually checks all 900 numbers (or all menu combinations). If the formula and the enumeration differ, it is almost always the formula that is wrong.

Walkthrough.

int b = 0;
for (int n = 100; n <= 999; n++) {
    int r = n / 100, p = (n / 10) % 10, s = n % 10;
    if (r == 7 || p == 7 || s == 7) b++;
}
cout << b << " " << 900 - 8 * 9 * 9 << "\n";   // 252 252

Tests. The answer program prints both numbers side by side:

a: 100 (rumus 4*5*5 = 100)
b: 252 (rumus 900 - 8*9*9 = 252)
c: 333 (rumus 250 + 166 - 83 = 333)
d: 36 (rumus 4*3*3 = 36)

If one of the lines does not match, it is not necessarily the formula that is wrong — the direct enumeration can also be wrong, for example because the loop range is 100 to 1000 instead of 100 to 999. The right habit: look for the difference on the smallest case, instead of immediately blaming one side.

Common mistakes.

• In part (d), counting the dessert as 2 choices, so the answer becomes 24. The phrase "may or may not be taken" adds one more state.
• Writing an enumeration that uses the same formula as the paper answer. The enumeration must be plain — check one by one.

Problem 3 — Passwords

Problem. Passwords of length n from k letters, at least one letter a, modulo 10⁹ + 7.

How to think about it. Complement: all passwords kⁿ, those without the letter a number (k−1)ⁿ. The answer is the difference. Since n goes up to 10¹⁸, both are computed with fast modular exponentiation (Chapter 14).

One modulo trap: the result of the subtraction can be negative after taking the modulo. Normalize it by adding MOD once more.

Walkthrough.

long long semua = pangkat_mod(k, n, MOD);
long long tanpa_a = pangkat_mod(k - 1, n, MOD);

cout << ((semua - tanpa_a) % MOD + MOD) % MOD << "\n";

Check with 4 26: the result is 66,351, the same as the direct enumeration in the chapter example.

Tests.

The first row is worth testing because the complement formula there gives 1 − 0: if there is only one letter and that letter is a, there is no password "without a". The last row tests fast modular exponentiation — with an ordinary loop, the program would never finish.

Common mistakes.

• Printing semua - tanpa_a ("all minus without a") without normalizing the negative sign.
• Computing kⁿ with a loop of n iterations.
• Forgetting the case k = 1: every password contains only the letter a, and (k−1)ⁿ = 0 — the formula is still correct.

Problem 4 — Inclusion-exclusion

Problem. From 1 to n (≤ 10¹⁸), those divisible by p or q.

How to think about it. The number of multiples of p up to n is n / p (integer division). The intersection is the multiples of LCM(p, q).

The big trap: the LCM of two numbers close to 10¹⁸ far exceeds the long long limit. Yet if the LCM alone is already larger than n, the intersection term is zero — its exact value is not needed. So first check whether the multiplication would exceed n:

Walkthrough.

long long calon = p / fpb(p, q);
long long jawab = n / p + n / q;

if (calon <= n / q) {          // calon * q will not exceed n
    long long k = calon * q;
    jawab -= n / k;
}

cout << jawab << "\n";

Check: 100 3 5 gives 47; 1000 4 6 gives 333.

Tests.

The second row is a good cross-check: the answer must equal your hand computation in problem 1c. The third row is the reason the LCM is computed as p / fpb(p, q) * q: with p * q first, numbers that large already overflow before they can be used.

Common mistakes.

• Using p * q as the intersection instead of the LCM. Wrong unless p and q are coprime.
• Computing the LCM without an overflow guard, then getting a negative number that makes n / k behave strangely.
• Enumerating one by one with a loop up to n. For 10¹⁸, impossible.

Challenge — Three sets

Problem. Divisible by at least one of three numbers.

The formula (seven terms).

n/p + n/q + n/r
  − n/LCM(p,q) − n/LCM(p,r) − n/LCM(q,r)
  + n/LCM(p,q,r)

The pattern: single terms are added, pair terms are subtracted, triple terms are added again. For m sets there are 2ᵐ − 1 terms, with the sign alternating according to the number of sets involved.

How to think about it. Every LCM is computed with the same guard as in problem 4. The triple LCM is computed step by step: LCM(LCM(p, q), r) — and if the pair LCM alone already exceeds n, the term can be skipped.

Walkthrough. See 05-tiga-himpunan.cpp. The checking part:

if (n <= 10000) {
    long long cacah = 0;
    for (long long i = 1; i <= n; i++)
        if (i % p == 0 || i % q == 0 || i % r == 0) cacah++;
    cout << "cacah langsung: " << cacah << "\n";
}

Check: 100 2 3 5 gives 74 from the formula and 74 from the enumeration; 10000 4 6 15 gives 3,666 from both.

Tests. The answer program prints the formula and the direct enumeration together:

The second case deliberately uses three numbers that are not coprime: the intersection of 4 and 6 is the multiples of 12 (not 24), the intersection of 4 and 10 is the multiples of 20 (not 40), and the intersection of all three is the multiples of 60. A formula that uses the product instead of the LCM will miss here, while on 100 2 3 5 it happens to be correct because all three are coprime.

Common mistakes.

• Swapping the sign on the triple term. If + is replaced with −, the numbers divisible by all three are not counted at all.
• Computing the triple LCM as p * q * r.
• Forgetting to test the formula with direct enumeration. A seven-term formula is easy to mistype, and enumeration for n ≤ 10,000 catches it within a second.

OSN-style exercises — walkthrough

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

Problem 1 — Colored Flag

How to think about it. Color from left to right. The first stripe has no left neighbor, so it is free: K choices. Every following stripe is forbidden only one color, namely the color of its left neighbor — whatever that color is, there is always exactly one forbidden, so there are always K − 1 choices.

Since every decision stands on its own once the previous decision is fixed, the product rule applies:

K × (K − 1) × (K − 1) × … = K × (K − 1)^(N−1)

An exponent as large as 10¹⁸ is computed with fast modular exponentiation from Chapter 14.

Walkthrough.

long long hasil = k % MOD * pangkat(k - 1, n - 1) % MOD;
cout << hasil << "\n";

Edge cases. The formula is already correct for both without an extra branch:

• N = 1: the power becomes (K − 1)^0 = 1, so the answer is K.
• K = 1 and N ≥ 2: the power is 0^(N−1) = 0, so the answer is 0 — indeed there is no valid flag, because two adjacent stripes are necessarily the same color.

Tests.

For 3 3, the answer can be enumerated by hand or with an enumerating program — and it is indeed 12.

Common mistakes.

• Writing K^N, forgetting the neighbor restriction.
• Writing K × (K − 1)^N, with the wrong exponent.
• Forgetting k % MOD before multiplying. For K ≤ 10⁹ the result happens to still be correct, but the habit of reducing every factor is safer.

Problem 2 — Password With Two Required Letters

How to think about it. Counting "contains a and contains b" directly is hard. Count the complement.

Let S be the set of all words of length N, of size K^N. Let A be the set of words that do not contain a, of size (K − 1)^N because every position has K − 1 choices. Let B be the set of words that do not contain b, also of size (K − 1)^N.

The invalid words are members of A or members of B. By inclusion-exclusion:

|A ∪ B| = |A| + |B| − |A ∩ B| = 2(K−1)^N − (K−2)^N

The intersection A ∩ B is the words that contain neither a nor b, of size (K − 2)^N. So the answer is:

K^N − 2(K−1)^N + (K−2)^N

Walkthrough.

long long semua = pangkat(k, n);
long long tanpaSatu = pangkat(k - 1, n);
long long tanpaKeduanya = pangkat(k - 2, n);

long long hasil = ((semua - 2 * tanpaSatu % MOD) % MOD + tanpaKeduanya) % MOD;
hasil = (hasil % MOD + MOD) % MOD;

The last line is what keeps the result from ever being negative. Without it, the program can print a negative number for completely valid input — a symptom that does not show up on the sample.

Tests.

The case 3 2 is worth enumerating by hand: of the eight words over a and b, those containing both are all except aaa and bbb, so 6.

Common mistakes.

• Using the formula K^N − (K−2)^N. That is the answer for "contains a or b", a different problem.
• Forgetting the + MOD adjustment after the subtraction.
• Computing 2 * tanpaSatu without % MOD, which for values close to the modulus is still safe in long long but breaks the standard form you should get used to.

Problem 3 — Pairs Summing to a Multiple of K

How to think about it. Whether x + y is divisible by K is determined only by the remainder of x and the remainder of y, not by their values. So group the numbers 1 to N by their remainder modulo K, then pair up the groups.

If x has remainder r, then y must have remainder K − r — except for r = 0, whose partner is also 0. The form (K − r) % K handles both at once.

The number of numbers from 1 to N with remainder r:

• for r = 0: ⌊N / K⌋
• for r ≥ 1: ⌊(N − r) / K⌋ + 1, and 0 if r > N

The answer is the sum of cacah[r] × cacah[(K − r) % K] over all r. Since the pairs are ordered, there is no division by two at the end.

Walkthrough.

vector<long long> cacah(k, 0);
cacah[0] = n / k;
for (long long r = 1; r < k; r++) {
    if (r > n) break;
    cacah[r] = (n - r) / k + 1;
}

long long hasil = 0;
for (long long r = 0; r < k; r++) {
    hasil += cacah[r] * cacah[(k - r) % k];
}

The cost is proportional to K, not N — 10⁶ steps for the largest constraints.

Size of the answer. The largest case is K = 1, when every pair qualifies: N² = 10¹⁸. It fits in long long, and this is why the constraint on N in this problem is smaller than in the two previous problems.

Tests.

The case 7 10 tests remainders that never appear: the groups r = 8 and onward are empty, and the product must yield zero, not read outside the array.

Common mistakes.

• Using cacah[k - r] without % k, which for r = 0 reads cacah[k] — out of bounds.
• Dividing the result by 2. The pairs are ordered, so there is no division.
• Checking every pair (x, y) with nested loops.

If you are still stuck

• Unsure whether to add or multiply → Chapter 16, the "or/and" table and the tree diagram.
• Something is counted twice → Chapter 16, section When the groups overlap.
• "At least one" problems feel hard → Chapter 16, the complement technique.

The most useful habit from this chapter: every counting formula is checked with direct enumeration on small data before it is used on large data.