notes.html
problem 4 · 33 lines
<article>
<h3>Problem Analysis</h3>
<p>
A <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindromic number</a> reads identically forwards and backwards, like 906609. I want the largest such <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> that can be written as the product of two n-digit numbers. The naive way to think about it is to enumerate every pair of n-digit factors and test each product: with 900 three-digit numbers that is roughly 900 x 900 = 810,000 pairs for n = 3, which is cheap, but the work is <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity#Quadratic_time" rel="noopener noreferrer" target="_blank">quadratic</a> in the count of n-digit values, scaling as <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(d^2)</a> where d = 9 x 10^(n-1). At n = 5 that is 90,000^2 = 8.1 billion pairs, far too many to walk blindly.
</p>
<p>
The observation that makes the search tractable is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Number_theory" rel="noopener noreferrer" target="_blank">number-theoretic</a> fact about even-length <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindromes</a>: every <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> with an even number of digits is <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisibility_rule" rel="noopener noreferrer" target="_blank">divisible</a> by 11. The cleanest way to see this is with <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modular arithmetic</a>: because 10 is congruent to -1 modulo 11, the power 10^k alternates between +1 and -1 as k changes parity. In an even-length <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> the two equal digits of each symmetric pair sit at positions whose exponents have opposite parity, so each pair contributes 10^i + 10^j congruent to 1 + (-1) = 0 modulo 11. The whole number is therefore <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisibility_rule" rel="noopener noreferrer" target="_blank">divisible</a> by 11. Since the product a x b equals such a <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> and 11 is <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a>, at least one of a or b must itself be <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisibility_rule" rel="noopener noreferrer" target="_blank">divisible</a> by 11. That single fact lets me step the inner loop by 11 instead of by 1, skipping ten of every eleven candidates. Combined with iterating downward (so large products surface first) and a <a class="reference-source" href="https://en.wikipedia.org/wiki/Monotonic_function" rel="noopener noreferrer" target="_blank">monotonicity</a>-based early exit, the practical running time drops to microseconds even at n = 5. The <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> test itself is <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(d)</a> in the digit count d, so the pruned pair enumeration dominates the cost.
</p>
<h3>Solution Approach</h3>
<h4>Pruned Descending Enumeration with 11-Divisibility Stepping (Python and C)</h4>
<p>
Both files implement the same algorithm, so I describe it once and note the language differences at the end.
</p>
<p>
<strong>Step 1 - Set up bounds.</strong> For scale n, the largest n-digit number is <code>max_number = 10^n - 1</code> and the smallest is <code>min_number = 10^(n-1)</code>. I also precompute <code>max_multiple_11 = max_number - max_number % 11</code>, the largest multiple of 11 not exceeding <code>max_number</code>. That value is the starting point for the inner loop whenever <code>a</code> is not itself a multiple of 11.
</p>
<p>
<strong>Step 2 - Outer loop descending.</strong> I iterate <code>a</code> from <code>max_number</code> downward. Descending order means the first <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindromes</a> I encounter tend to be large, which raises the best-known value quickly and makes the inner early-exit fire sooner.
</p>
<p>
<strong>Step 3 - The 11 split.</strong> If <code>a</code> is already a multiple of 11, the <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisibility_rule" rel="noopener noreferrer" target="_blank">divisibility</a> constraint is satisfied no matter what <code>b</code> is, so <code>b</code> steps by 1 starting from <code>max_number</code>. Otherwise <code>b</code> must supply the factor of 11, so <code>b</code> steps by 11 starting from <code>max_multiple_11</code>. This is the core optimisation: in the common case it discards ten of every eleven inner iterations.
</p>
<p>
<strong>Step 4 - Early termination.</strong> Inside the inner loop I compute <code>ab = a * b</code> and break immediately if <code>ab <= largest_palindrome</code>. Because <code>a</code> is fixed and <code>b</code> only decreases, <code>ab</code> is <a class="reference-source" href="https://en.wikipedia.org/wiki/Monotonic_function" rel="noopener noreferrer" target="_blank">monotonically</a> decreasing, so once it falls to or below the best <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> already found, no later <code>b</code> can beat it.
</p>
<p>
<strong>Step 5 - Palindrome test.</strong> I convert the product to a string and check whether it equals its reverse. If so, I record the new best. The C version additionally breaks out of the inner loop on the first <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> found, which is valid given the descending order: for a fixed <code>a</code>, the first <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> encountered is the largest possible for that <code>a</code>.
</p>
<p>
<strong>Language differences.</strong> The Python version builds the reversed string with <code>"".join(reversed(str_number))</code> and compares. The C version writes the number into a stack buffer with <code>snprintf</code> and walks <a class="reference-source" href="https://en.wikipedia.org/wiki/Two_pointers_technique" rel="noopener noreferrer" target="_blank">two pointers</a> inward, avoiding any heap allocation. The C inner loop also explicitly breaks after recording a <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a>; Python omits that extra break, but its <code>ab <= largest_palindrome</code> guard achieves the same prune on the very next iteration. Both compute identical results.
</p>
</article>