notes.html

problem 62 · 73 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem asks me to find the smallest perfect cube whose digits can be rearranged into exactly
five distinct cubes (counting the cube itself). The mathematical core is the notion of a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a>
of digits: two numbers are digit-permutations of one another precisely when they contain the same
digits in the same counts - that is, they share the same
<a class="reference-source" href="https://en.wikipedia.org/wiki/Multiset" rel="noopener noreferrer" target="_blank">multiset</a>
of digits. The observation that makes this tractable is that I can convert this "equal up to
reordering" relation into an exact equality test by computing a canonical form. If I sort the digits
of a number into ascending order and join them back into a string, then two numbers are
digit-permutations of each other if and only if their sorted-digit strings are identical. That sorted
string becomes a shared key for every member of a permutation class, collapsing an exponential
equivalence relation into a single
<a class="reference-source" href="https://en.wikipedia.org/wiki/Hash_table" rel="noopener noreferrer" target="_blank">hash table</a>
lookup.
</p>
<p>
The second key insight is that permutations of a number always have the same number of digits.
Therefore all cubes that could possibly be permutations of one another live in the same digit-length
band, and I can process cubes batch by batch - one digit-length at a time - grouping each batch by its
canonical key. As soon as I find a digit-length where some group has exactly the target size, the
smallest cube in that group is the answer; because I processed shorter numbers first, no smaller cube
can qualify. The count of d-digit cubes is roughly proportional to 10^(d/3) (the cube root of a
d-digit number has about d/3 digits), and each cube costs O(d log d) to sort its digits. The overall
work is therefore O(10^(d/3) * d log d) up to the answer's length, which is small enough that every
test case finishes in well under 100 ms.
</p>
<h3>Solution Approach</h3>
<h4>Digit-canonical grouping by digit-length band</h4>
<p>
Both the Python and C files implement the identical algorithm; they differ only in how the grouping
map is realised.
</p>
<p>
<strong>Step 1 - Bound the range of d-digit cubes.</strong> For a target digit-length d, the smallest
d-digit number is 10^(d-1) and the largest is 10^d - 1. I need the integers whose cubes fall in this
band, so I take the cube root of each bound. I use <code>ceil(cbrt(...))</code> on the lower bound as
the inclusive start, and <code>ceil(cbrt(...)) + 1</code> on the upper bound as the exclusive stop.
Using the ceiling rather than a floor or a bare cast guards against a slightly-under
<a class="reference-source" href="https://en.wikipedia.org/wiki/Floating-point_arithmetic" rel="noopener noreferrer" target="_blank">floating-point</a>
representation of an exact root pulling in a cube from the wrong digit band.
</p>
<p>
<strong>Step 2 - Build the canonical-key map.</strong> For each integer i in the range I compute i^3,
convert it to a decimal string, sort the characters, and use that sorted string as a key into a map
whose values are lists of cubes sharing that key. In Python this is
<a class="reference-source" href="https://docs.python.org/3/library/collections.html#collections.defaultdict" rel="noopener noreferrer" target="_blank">collections.defaultdict(list)</a>
with <code>permuted_cubes[key].append(cube)</code>. In C it is a custom hash table with 65536 buckets,
each chaining entries that hold a dynamically growing <code>long long</code> array.
</p>
<p>
<strong>Step 3 - Scan for groups of the target size.</strong> Once the batch is fully grouped, I
examine every entry whose list has exactly <code>num_permutations</code> members. Each such group is a
candidate, and its answer is the minimum cube in the group. I take the minimum over all qualifying
groups at this digit-length.
</p>
<p>
<strong>Step 4 - Advance.</strong> If no group qualified, I increment the digit-length and repeat. The
first digit-length that yields a result holds the globally smallest answer, since all shorter cubes
were already exhausted.
</p>
<p>
<strong>Language-specific differences.</strong> Python leans entirely on the built-in dictionary,
which handles hashing and resizing transparently. The C version replicates these semantics by hand: a
power-of-two bucket array, a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Daniel_J._Bernstein" rel="noopener noreferrer" target="_blank">djb2</a>
string hash, and amortised-doubling value arrays. The extra effort buys roughly a 2x speedup, but both
stay comfortably fast.
</p>
</article>