notes.html

problem 52 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
The mathematical core of this problem is the notion of a <em>digit multiset</em>: two integers are <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutations</a> of one another exactly when they contain the same decimal digits with the same multiplicities, irrespective of order. The challenge is to test this relation cheaply. My tool is a <em>canonical form</em> - a single, unique representative chosen for each class of digit-permutations. The obvious choice is the string of the number's decimal digits <a class="reference-source" href="https://en.wikipedia.org/wiki/Sorting_algorithm" rel="noopener noreferrer" target="_blank">sorted</a> into ascending order. I call this a <em>fingerprint</em>. Two numbers are digit-permutations of each other if and only if their fingerprints are identical, so the awkward question "do these share the same digits?" collapses into a plain string equality test.
</p>
<p>
The second observation bounds the search and proves that <a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute force</a> is safe. If <code>x</code> has <code>d</code> decimal digits, any permutation of <code>x</code> must also have exactly <code>d</code> digits. Therefore <code>x</code>, <code>2x</code>, ..., <code>6x</code> must all have the same digit count. Since <code>6x</code> is the largest, this forces <code>x</code> into the lower sixth of its digit-length band (roughly <code>x &lt; 10^d / 6</code>); otherwise <code>6x</code> would carry into the next band and gain a digit. Consequently the answer is never far from the start of any band, and a simple upward linear scan finds 142857 after about 140,000 iterations. The total work is <code>O(N * M * D)</code> where <code>N</code> is the answer, <code>M</code> the number of multiples (at most 6), and <code>D</code> the digit count (at most 7) - trivially small.
</p>
<h3>Solution Approach</h3>
<h4>Linear Scan with Sorted-Digit Fingerprinting (Python and C)</h4>
<p>
Both files implement the same algorithm. I iterate over candidates <code>x = 1, 2, 3, ...</code>. For each <code>x</code> I compute the fingerprint of every required multiple and check whether they all agree with the fingerprint of <code>x</code> itself. The first <code>x</code> for which they all coincide is the answer.
</p>
<p>
In Python I express the test with a set comprehension: <code>{"".join(sorted(str(i * multiple))) for multiple in multiples_range}</code>. Building a <a class="reference-source" href="https://docs.python.org/3/tutorial/datastructures.html#sets" rel="noopener noreferrer" target="_blank">set</a> collapses duplicate fingerprints, so if every multiple shares the same digits the set has exactly one element. The condition <code>len(...) == 1</code> therefore reads as "all fingerprints are equal." I bound the loop at <code>sys.maxsize // multiples</code> as a conceptual overflow guard, though Python integers are unbounded in practice.
</p>
<p>
In C I implement fingerprinting by hand. The <code>sorted_digits</code> function extracts digits by repeatedly taking <code>n % 10</code> and dividing by 10, writing them into a buffer, then calls <a class="reference-source" href="https://en.cppreference.com/w/c/algorithm/qsort" rel="noopener noreferrer" target="_blank">qsort</a> to sort that buffer and null-terminates it. I compare fingerprints with <a class="reference-source" href="https://en.cppreference.com/w/c/string/byte/strcmp" rel="noopener noreferrer" target="_blank">strcmp</a>. Crucially I use an <em>early exit</em>: in the inner loop over multiples 2..M, the moment a multiple fails to match I set <code>all_match = 0</code> and <code>break</code>. Because the vast majority of candidates fail at the very first multiple (<code>m = 2</code>), most iterations do only a single comparison.
</p>
<p>
Both versions take the number of multiples as a parameter (a command-line argument in C, a positional argument in Python), so the same code verifies the simpler 2-multiple case (answer 125874, given in the statement) as well as the full 6-multiple case.
</p>
</article>