Problem Analysis
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 permutation 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 multiset 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 hash table lookup.
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.
Solution Approach
Digit-canonical grouping by digit-length band
Both the Python and C files implement the identical algorithm; they differ only in how the grouping map is realised.
Step 1 - Bound the range of d-digit cubes. 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 ceil(cbrt(...)) on the lower bound as
the inclusive start, and ceil(cbrt(...)) + 1 on the upper bound as the exclusive stop.
Using the ceiling rather than a floor or a bare cast guards against a slightly-under
floating-point
representation of an exact root pulling in a cube from the wrong digit band.
Step 2 - Build the canonical-key map. 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
collections.defaultdict(list)
with permuted_cubes[key].append(cube). In C it is a custom hash table with 65536 buckets,
each chaining entries that hold a dynamically growing long long array.
Step 3 - Scan for groups of the target size. Once the batch is fully grouped, I
examine every entry whose list has exactly num_permutations 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.
Step 4 - Advance. 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.
Language-specific differences. 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 djb2 string hash, and amortised-doubling value arrays. The extra effort buys roughly a 2x speedup, but both stay comfortably fast.