Discovering patterns by enumeration

Some contest problems have no obvious formula or algorithm waiting to be spotted from the statement alone. The answer follows a pattern you have to discover for yourself: write a brute force that works on small inputs, run it across many small cases, look for a pattern in the results, and only then implement that pattern for the real input sizes.

This shows up often in senior contests. The pattern you find might be a closed formula, a recurrence, or a rule tied to some property of the input, such as parity or a prime factorization. Once you see it, the rest of the problem is usually easy.

Write a brute force first

Start with code that is correct on small inputs, even if it is much too slow for the real constraints. Do not think about efficiency yet; a brute force can check every possibility, try every permutation, or explore every branch of a recursion, as long as it gets the right answer.

Take this question: given N, in how many ways can N be written as a sum of distinct powers of 2? A brute force checks every subset of 2^0, 2^1, 2^2, ... up to the largest power at or below N, and counts how many subsets sum to N. It is slow for large N, but for small N it runs instantly.

Enumerate and tabulate

Run the brute force across a range of small inputs, and write down input alongside answer.

For the powers-of-2 question, running it for N = 1 through 8 gives:

1N: 1, answer: 12N: 2, answer: 13N: 3, answer: 14N: 4, answer: 15N: 5, answer: 16N: 6, answer: 17N: 7, answer: 18N: 8, answer: 1

Every single answer is 1. That is already the pattern: no matter which N you try, there is exactly one way to write it as a sum of distinct powers of 2. This is really a familiar fact wearing a different name: it is the statement that every number has exactly one binary representation. Enumeration did not just help find a fast formula here, it revealed that the "hard" combinatorial question was actually asking about something you already knew.

Spot the pattern

A discovered pattern usually takes one of a few shapes: a closed formula like N or N * (N + 1) / 2, a recurrence like Fibonacci's F(N) = F(N-1) + F(N-2), or a rule tied to a property of N, such as its parity or whether it is prime. Whichever shape it takes, write the hypothesis down in words or in a formula before you trust it. Noticing that "it looks kind of linear" is not the same as stating exactly what the rule is.

Verify on more cases

Test the hypothesis against more inputs than the ones that suggested it, and make edge cases part of that test, not an afterthought. If it fails on even one case, the hypothesis is wrong, not the input: go back, look for what property distinguishes the failing case, and revise.

Generate the extra test cases either by hand or by letting the slow brute force run a bit longer. It does not need to be fast, it only needs to reach far enough past your smallest examples to catch a hypothesis that was really only true by coincidence for tiny N.

A worked example

Here is a question where the pattern is less obvious on sight: given N, find the single digit you reach by repeatedly replacing N with the sum of its digits, until only one digit is left.

1def digit_sum(n):2    total = 03    while n > 0:4        total += n % 105        n //= 106    return total7
8
9def digital_root_bruteforce(n):10    while n >= 10:11        n = digit_sum(n)12    return n13
14
15n = 987516print(digital_root_bruteforce(n))

2

For N = 9875, one round of summing gives 9 + 8 + 7 + 5 = 29, then 2 + 9 = 11, then 1 + 1 = 2, and the program prints 2. Running the same brute force for N = 1 through 20 gives 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2. The nine-digit block repeats exactly: after 9, the sequence resets to 1 and counts up again. That points straight at a formula built from remainders mod 9: the answer is 1 + (N - 1) % 9. Check it against 9875: (9875 - 1) % 9 is 1, so the formula gives 1 + 1 = 2, matching the brute force exactly.

Implement the pattern

Once you trust the hypothesis, stop running the brute force on the real test cases and implement the pattern directly instead: code the formula if it is a formula, or the recurrence, with memoization, if it is a recurrence.

Before submitting, check the fast implementation against the slow brute force on the same small inputs that led you to the pattern in the first place. If they disagree anywhere, the hypothesis missed a case; if a submission still comes back wrong after that check, the fix is more brute-force cases, not a rewrite of the formula you have not yet re-verified.

Second worked example: the staircase sum

A more familiar example: given N, find the sum of the first N positive integers. The brute force is a single loop, adding 1 through N. Tabulating N = 1 through 6 gives 1, 3, 6, 10, 15, 21.

Pair the first and last terms of the sum: 1 and N add to N + 1, 2 and N − 1 add to N + 1, and every other pair does too, so N/2 pairs each worth N + 1 give a total of N * (N + 1) / 2. That is the closed formula, and it answers in O(1) what the loop answers in O(N).

Getting pattern discovery right

The most common failure is trusting a pattern before it has been stress-tested. A handful of small cases can look linear and turn out to be quadratic once N grows past what you checked by hand; test at least a dozen or two cases, and make sure 0, 1 and a couple of large values are among them.

A close second is spotting a pattern and coding it straight from memory without checking it against the brute force output one more time. The pattern that looked right in your head is not the same as the pattern verified against real data, and only the second one belongs in a submission.

And not every pattern is a single tidy formula. Some are piecewise, with a different rule for even and odd N; some involve a modulus, the way the digital-root example did; some are a known sequence like Fibonacci in disguise. If the first formula you try does not fit every case, look for a rule tied to a property of N instead of forcing a formula that almost works.

Why enumeration is powerful

Enumeration trades analysis for observation: instead of deriving the answer mathematically, you let a slow program explore small cases and you read the pattern off the results. It works because many contest answers have a simple, elegant shape that is much easier to recognize from a table of values than to derive from the problem statement cold.

The brute force only has to run once, during your own exploration; the fast pattern you extract from it answers every real test case in a fraction of the time. The one real risk is a pattern that only looked right on the cases you happened to check. That is exactly why verifying against the brute force, on cases beyond the ones that first suggested the pattern, is not an optional step.