Thinking before coding with small cases, brute force and patterns

Why this matters when you build with AI

An AI coding tool can write a counting formula in one line. The line often looks right. The usual failure is that the formula fits the two or three samples in the statement and breaks on the fourth or fifth case. You cannot see this by reading the formula, because it looks equally confident in both cases.

The habit this lesson teaches is to get true answers for small inputs first. You write a slow program that is simple enough to trust, and you let it print a table of answers for n = 1, 2, 3 and so on. Then you look for a pattern in the table. Only after that do you write a fast method. The table then is a test: the fast method must match every row, and it must also match many larger values that you did not look at while you were guessing.

A brute force is a program that tries every candidate answer and counts the good ones. It is slow, but it is short, and you can check it by reading. A table is the list of answers for n = 1, 2, 3 and so on. A pattern is a rule that the table follows. A closed form is a formula that gives the answer for any n in a fixed number of steps, with no loop over n. Parity means whether a number is even or odd.

This lesson uses C++17 for the programs and Python for the table reading and the checks. We compiled with g++ 15.2.0 on Ubuntu and ran Python 3.14.4. Your output may differ in timing, but the counts do not depend on the machine.

The idea: four steps

The method has four steps. Do them in order.

Small cases by hand. Take n = 1, 2 and 3. Write down every candidate and decide by hand whether it counts. This shows you what the statement means. Many wrong solutions come from a misreading, such as < where <= was meant, and the hand work catches it before any code.
A brute force that prints a table. Write the slowest program that is obviously correct. Let it print the answer for each n from 1 to about 12. You trust this table more than any formula you have not checked.
Patterns from the table. Look at the differences, which means the change from one row to the next, T(n) - T(n-1) for an answer T(n). Look at the parity of n, because many counting answers split into an even case and an odd case. Look at the growth, which tells you the degree of the formula. If the differences themselves follow a clear rule, the answer does too.
A fast method, checked. Write the formula or fast algorithm. Test it on every row of the table, then on many more values from the brute force, and then on a few large values using a second method that is slower but independent of the formula.

Step 4 is where most people stop too early. A formula that matches n = 1 to 6 may still be wrong at n = 7, especially when the pattern has a parity split.

Why small inputs are enough to find a pattern

A pattern is a guess, so you need enough data to make the guess hard to fake. Four numbers are not enough, because a cubic polynomial has four free coefficients, and any four points lie on some cubic. Eight to twelve rows are a good start. You can then test the guess on rows you did not use to make it.

Small inputs are not enough for a proof. A formula that holds for n up to 300 is strong evidence, but only the reasoning behind it proves it for every n. The worked example below gives that reasoning.

Worked example: triples with an even sum

Here is an original problem written for this lesson.

You are given one integer n. Count the triples of integers (a, b, c) with 1 <= a <= b <= c <= n such that a + b + c is even. Input: one line with n. Output: the count. Constraints: 1 <= n <= 10^6.

The answer can be large, so we use a 64-bit integer. For n = 10^6 the answer is about 8.3 × 10^16, far above the 32-bit limit of about 2.1 × 10^9.

Read the statement twice. The inequalities are not strict, so a = b and b = c are allowed. The triple is ordered, meaning a is the smallest and c is the largest, so each set of three values is counted once.

Step 1: small cases by hand

For n = 1 there is one triple, (1, 1, 1). Its sum is 3, which is odd. The answer is 0.

For n = 2 there are four triples. Their sums are:

(1, 1, 1)  sum 3  odd, no
(1, 1, 2)  sum 4  even, yes
(1, 2, 2)  sum 5  odd, no
(2, 2, 2)  sum 6  even, yes

The answer is 2.

For n = 3 there are ten triples. Write them all down, in order, so that you do not skip any:

(1,1,1) 3 no    (1,1,2) 4 yes   (1,1,3) 5 no    (1,2,2) 5 no    (1,2,3) 6 yes
(1,3,3) 7 no    (2,2,2) 6 yes   (2,2,3) 7 no    (2,3,3) 8 yes   (3,3,3) 9 no

The answer is 4.

Look at the triples that are new when n goes from 2 to 3. They are the ones whose largest value is 3, namely (1,1,3), (1,2,3), (1,3,3), (2,2,3), (2,3,3) and (3,3,3). Two of them count. This already suggests the method: the change from one row to the next counts the triples whose largest value is the new n.

Hand work is quick for n = 3, but it gets slow for n = 12, and it is easy to skip a line. That is why the next step is a program.

Step 2: a brute force that prints the table

The program below tries every triple with a <= b <= c <= n, and prints the count for each n from 1 to 12. The loops are nested, so the cost grows with the cube of n, which is fine for small n.

#include <bits/stdc++.h>
using namespace std;
// Count triples (a, b, c) with 1 <= a <= b <= c <= n and a + b + c even.
// Brute force: try every triple. Prints one row per n.
int main() {
    int N = 12;
    for (int n = 1; n <= N; n++) {
        long long count = 0;
        for (int a = 1; a <= n; a++)
            for (int b = a; b <= n; b++)
                for (int c = b; c <= n; c++)
                    if ((a + b + c) % 2 == 0) count++;
        cout << n << ' ' << count << '\n';
    }
}

Compile it with the sanitizer flags from the contest template lesson, and with the warning flags:

g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wconversion -fsanitize=address,undefined -fno-sanitize-recover=all table.cpp -o table
./table

The compile step gave no warnings. This is the real output of our run:

The rows for n = 2 and n = 3 match the hand work above.

Step 3: differences and parity

Next, write the differences. The table is short, so a few lines of Python are enough. This script is self-contained and does not read input. It recomputes the table with the same loops, prints the answer T(n), the difference D(n) = T(n) - T(n-1), the value n // 2 (integer division, which drops the remainder), and the product m * (m + 1) with m = n // 2.

Python · editable

Real output:

n  T(n)  D(n)  n//2  (n//2)*(n//2+1)
1  0     0     0     0
2  2     2     1     2
3  4     2     1     2
4  10    6     2     6
5  16    6     2     6
6  28    12    3     12
7  40    12    3     12
8  60    20    4     20
9  80    20    4     20
10 110   30    5     30
11 140   30    5     30
12 182   42    6     42

The differences come in equal pairs: 2, 2, 6, 6, 12, 12, 20, 20, 30, 30, 42. The pairs are (n = 2, n = 3), (n = 4, n = 5) and so on. So the pattern depends on the parity of n, and it is the same for n = 2k and n = 2k + 1. The last column shows the rule: the difference is m * (m + 1) with m = n // 2. The pattern holds for every row from n = 1 to n = 12.

The table also shows the growth. The differences grow like the square of m, so the answer grows like the cube of n. That is what you would expect: the answer is a count of triples, and there are about n³/6 triples in total.

Why AI tools fail at this step

Suppose you ask a tool for a formula after showing it only the first four answers, 0, 2, 4 and 10. A cubic polynomial passes through any four points, so the tool can return one that fits perfectly and still be wrong. Here is what a cubic through those four points predicts for later rows, computed with exact fractions:

n = 1..8 predicted by the cubic: 0, 2, 4, 10, 24, 50, 92, 154
true answers from the table:     0, 2, 4, 10, 16, 28, 40, 60

At n = 5 the cubic says 24 and the true answer is 16. The cubic is wrong because the true answer is not one polynomial in n. The parity split means it is a polynomial in each parity class, and each class has its own formula.

The check is simple: give the tool more rows, not fewer, and ask it to test its formula on rows you did not show it. Ask for the brute force first, and hold back the formula until the table exists:

Write a C++17 program that counts the triples (a, b, c) with 1 <= a <= b <= c <= n
and a + b + c even. Use three nested loops with exactly these bounds. Read n from
input, then print the count for n = 1 to 12, one line per n. Do not give a formula.

A good answer has three nested loops, with b starting at a and c starting at b, and it prints twelve lines. Check the first three lines by hand against the hand work above before you trust the table.

Step 4: why the difference rule holds

A pattern in a table is a guess until you give a reason for it. Here is a short counting argument for D(n) = m * (m + 1), with m = n // 2.

The difference D(n) is the number of triples whose largest value is exactly n. Such a triple is (a, b, n) with 1 <= a <= b <= n. It counts when a + b + n is even.

Let o be the number of odd values in 1 to n and e the number of even values. Then o = (n + 1) // 2 and e = n // 2. Count the pairs a <= b in two groups:

pairs where both values have the same parity. Both odd gives o(o+1)/2 pairs, and both even gives e(e+1)/2 pairs. Their sum is the number of pairs with a + b even.
pairs where the parities differ. Each such pair has one odd and one even value, and it is counted once, so there are o * e of them. These are exactly the pairs with a + b odd.

If n is even, n = 2q and o = e = q. We need a + b even, which gives q(q+1)/2 + q(q+1)/2 = q(q+1).

If n is odd, n = 2q + 1, so o = q + 1 and e = q. We need a + b odd, which gives (q+1) * q = q(q+1).

In both cases D(n) = q(q+1) with q = n // 2. That is the rule from the table, now proved.

Step 5: the closed form

The answer is the running total of the differences: T(n) is the sum of D(j) for j from 1 to n. Group the terms by k = j // 2. Each value k from 1 to q appears twice, once for j = 2k and once for j = 2k + 1, except that when n is even the last value k = q appears only once, for j = 2q.

If n = 2q is even, T = 2 * (sum of k(k+1) for k = 1..q-1) + q(q+1). This simplifies to q(q+1)(2q+1)/3.
If n = 2q + 1 is odd, T = 2 * (sum of k(k+1) for k = 1..q). This simplifies to 2q(q+1)(q+2)/3.

Check with the table: n = 4 gives q = 2 and 2 * 3 * 5 / 3 = 10. n = 5 gives q = 2 and 2 * 2 * 3 * 4 / 3 = 16. Both match.

The fast solution

The fast solution reads n and applies the two formulas. It does no loop over the triples.

#include <bits/stdc++.h>
using namespace std;
// Closed form from the table: with q = n / 2 (integer division),
// n even: q(q+1)(2q+1)/3      n odd: 2q(q+1)(q+2)/3
int main() {
    long long n;
    cin >> n;
    long long q = n / 2;
    long long ans;
    if (n % 2 == 0) ans = q * (q + 1) * (2 * q + 1) / 3;
    else            ans = 2 * q * (q + 1) * (q + 2) / 3;
    cout << ans << '\n';
}

Compile it with the same flags, and run it on the table rows:

g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wconversion -fsanitize=address,undefined -fno-sanitize-recover=all fast.cpp -o fast
for n in 1 2 3 4 5 6 7 8 9 10 11 12; do echo "$n" | ./fast; done

The output matches the table row by row: 0, 2, 4, 10, 16, 28, 40, 60, 80, 110, 140, 182.

The check calls three programs. The brute force is brute.cpp. It reads n and uses the same three loops as the table program, with the count printed for that one n. The formula is fast.cpp, shown above. The third program, slow_sum.cpp, is an O(n) check. It adds the differences m * (m + 1) one by one, so it does not depend on the closed form.

#include <bits/stdc++.h>
using namespace std;
// Independent O(n) check: the increase from n-1 to n is m(m+1) with m = n / 2.
int main() {
    long long n;
    cin >> n;
    long long total = 0;
    for (long long j = 1; j <= n; j++) {
        long long m = j / 2;
        total += m * (m + 1);
    }
    cout << total << '\n';
}

The Python check below runs the three programs and compares them.

import subprocess
 
# Compare the brute force and the closed form for every n from 1 to 300.
bad = []
for n in range(1, 301):
    inp = f"{n}\n"
    want = subprocess.run(["./brute"], input=inp, capture_output=True, text=True, timeout=60).stdout.strip()
    got = subprocess.run(["./fast"], input=inp, capture_output=True, text=True, timeout=10).stdout.strip()
    if want != got:
        bad.append((n, want, got))
print("checked n = 1..300, mismatches:", len(bad), bad[:5])
 
# Compare the O(n) sum with the closed form on a few large n.
for n in [1000, 99999, 1000000]:
    a = subprocess.run(["./fast"], input=f"{n}\n", capture_output=True, text=True, timeout=10).stdout.strip()
    b = subprocess.run(["./slow_sum"], input=f"{n}\n", capture_output=True, text=True, timeout=60).stdout.strip()
    print(f"n={n} fast={a} slow_sum={b} same={a == b}")

Real output of our run:

checked n = 1..300, mismatches: 0 []
n=1000 fast=83583500 slow_sum=83583500 same=True
n=99999 fast=83333333300000 slow_sum=83333333300000 same=True
n=1000000 fast=83333583333500000 slow_sum=83333583333500000 same=True

We did not run the brute force at n = 10^6. It makes about n³/6 steps, which is roughly 1.7 × 10^17, so it would never finish. That is the reason for the O(n) check instead: it is slow but still practical at this size.

Timing will differ on your machine. The counts will not.

Complexity

The brute force takes O(n³) time and O(1) extra memory. The formula takes O(1) time and O(1) memory. The O(n) sum takes O(n) time.

The values stay within 64 bits. For n = 10^6, the largest product in the formula is about q(q+1)(2q+1), which is about 2.5 × 10^17. The 64-bit limit is about 9.2 × 10^18, so there is room. In C++ the long long type is at least 64 bits. An int overflows in that product once n is about 2000.

Common mistakes

Fitting a polynomial to the first few rows. The symptom is a formula that matches n = 1 to 4 and gives 24 at n = 5, where the true answer is 16. Give the fit more rows and test it on rows you did not use.

Strict instead of non-strict inequalities. If both inner loops start one higher, with b = a + 1 and c = b + 1, the program counts only triples with a < b < c. For n = 3 that gives 1 instead of 4, since (1, 2, 3) is the only strictly increasing triple with an even sum. Check the loop bounds against the statement by hand for n = 2 or 3.

A table that is too short. With only three rows, the difference pairs do not show. You need eight to twelve rows before the parity split is visible.

Using one formula for both parities. Applying the even formula to odd n gives a wrong answer that is close to the right one, which is hard to notice. The symptom is a mismatch that appears only on odd rows. The fix is to branch on n % 2 as the fast solution does.

A passing table is not a proof. A formula that matches the table can still fail at a larger n if the pattern is coincidental. Test many more values, and give a reason for the pattern, as in Step 4.

Overflow in the formula. Using int for q(q+1)(2q+1) overflows for n of about 2000 and more, even though the answer itself is still small enough. The symptom is a negative or very wrong answer for large n only. Use long long for every intermediate product.

A brute force that shares your misreading. If you misread the statement, your brute force and your formula agree and both are wrong. The hand work for n = 1 to 3 is the only check that does not depend on the code. Do it first.

Checklist

Work n = 1, 2 and 3 by hand, and list every candidate.
Write the brute force first and make it obviously correct, even if it is slow.
Print a table of at least eight to twelve rows from the brute force.
Compute the differences and look for parity splits before you guess a formula.
Give a short counting reason for the pattern, or mark it as a guess.
Test the formula on every row of the table, then on many more values from the brute force.
Test a few large values with a second method that does not use the formula.
Use 64-bit integers for every intermediate product.
Keep the hand work and the table with the code, so you can check them later.

Hands-on exercise

Make a new folder on your machine. Save the table program as table.cpp, the brute force as brute.cpp, the formula as fast.cpp, and the O(n) sum as slow_sum.cpp. Save the Python check as check.py.

Write the answers for n = 1, 2 and 3 by hand, with every triple listed. Compare them with the table.
Build table.cpp and run it. Record the rows for n = 1 to 12.
Run the Python differences script from this lesson. Check that each difference pair repeats.
Build fast.cpp and run the check. Record the number of mismatches for n from 1 to 300.
In brute.cpp, change both inner loops so that b starts at a + 1 and c starts at b + 1. Run the table again, then the check. Record which rows change, and explain why the check fails.

Show the answer

Step 1: the answers are 0, 2 and 4, and the triples for n = 3 are the ten listed in the lesson. Step 2: your rows should match the table in the lesson. Step 3: the pairs are (2, 3), (4, 5), (6, 7), (8, 9) and (10, 11), each with equal differences. Step 4: the mismatch count should be 0. Step 5: the strict version gives 0 for n = 1, which is correct by chance, since the answer is 0 there. For n = 2 it gives 0 instead of 2, so the check fails from n = 2 on. For n = 3 it gives 1 instead of 4. The reason is that the strict loop drops every triple with a repeated value, such as (1, 1, 2), (2, 2, 2) and (2, 3, 3), so the brute force no longer matches the statement.

Practice problems

Work each problem by hand first, then check it in code.

Practice 1: odd sums by hand. For n = 3, count the triples (a, b, c) with 1 <= a <= b <= c <= 3 and a + b + c odd. Then say what the answer is for n = 3 with the even rule, and check that the two answers add up to the total number of triples.

Hint: you already have the ten triples for n = 3 and their sums in this lesson.

Show the answer

The even count is 4, so the odd count is 10 - 4 = 6. The triples with odd sum are (1,1,1), (1,1,3), (1,2,2), (1,3,3), (2,2,3) and (3,3,3). Together with the four even triples they make 10, which is the total number of triples with 1 <= a <= b <= c <= 3.

Practice 2: pairs with a sum divisible by 3. Count the pairs (x, y) with 1 <= x < y <= n and x + y divisible by 3, for 1 <= n <= 10^6. Write a brute force that prints the table for n from 1 to 12. Then find a formula from the table. Write the formula in terms of how many values in 1 to n have remainder 0, 1 and 2 when divided by 3.

Hint: let r0, r1 and r2 be those counts. Two values add to a multiple of 3 when both have remainder 0, or when one has remainder 1 and the other has remainder 2.

Show the answer

The table for n = 1 to 12 is 0, 1, 1, 2, 4, 5, 7, 10, 12, 15, 19, 22. Let r0 = n // 3, r1 = (n + 2) // 3 and r2 = (n + 1) // 3. Then the count of pairs is r0 * (r0 - 1) / 2 + r1 * r2. Check n = 12: r0 = 4, r1 = 4, r2 = 4, so the answer is 6 + 16 = 22, which matches the table. Check n = 7: r0 = 2, r1 = 3, r2 = 2, so the answer is 1 + 6 = 7. A Python brute force of this formula for every n from 1 to 399 found no mismatch. Your code should print the same table.

Practice 3: prove the difference rule. Using the counting argument in this lesson, explain in your own words why the number of triples with largest value n is m * (m + 1) with m = n // 2. Then check the argument for n = 5 by listing the pairs (a, b) with 1 <= a <= b <= 5 and a + b odd.

Hint: for n = 5 the triple sum is even when a + b is odd, because n is odd.

Show the answer

For n = 5, o = 3 (values 1, 3, 5) and e = 2 (values 2, 4). The pairs with a + b odd have one odd and one even value, so there are o * e = 6 of them: (1,2), (1,4), (2,3), (2,5), (3,4) and (4,5). Here m = 2, and m * (m + 1) = 6, which matches. The table says D(5) = 6, so the argument and the table agree.

Practice 4: check the arithmetic by hand. Use the even formula q(q+1)(2q+1)/3 with q = 500000 to compute the answer for n = 1000000 by hand, or with a calculator. Compare it with the value printed in this lesson, 83333583333500000.

Hint: compute q(q+1) first, then multiply by 2q+1, then divide by 3. Keep every step exact.

Show the answer

With q = 500000, we get q(q+1) = 500000 * 500001 = 250000500000. Next, 250000500000 * 1000001 = 250000500000 * 1000000 + 250000500000 = 250000500000000000 + 250000500000 = 250000750000500000. Dividing by 3 gives 83333583333500000, which matches the program output. Divide the full product, not a rounded piece of it, because the formula is exact only at that step.

Python notes

The table and the differences script above use Python, because the brute force is short and easy to read. For n up to about 60, a Python brute force is fast enough, since the number of triples is about n³/6. For the check up to n = 300 we used C++, because the brute force is then about 4.5 million steps for the largest n and Python would be slow on the full range.

Python integers never overflow, so the formula is safe in Python. That is a good reason to test a formula in Python first, and to write the contest version in C++ with the 64-bit checks.

Summary

Work small cases by hand, print a table of true answers from a brute force, read the differences and the parity, and only then write the fast method. Test it on every row and on many more values, and treat a passing table as evidence until you have a reason for the pattern.