We seek the smallest cube for which exactly five permutations of its decimal digits are also cubes. The key word is exactly: a signature that produces five cubes is valid only if no sixth cube with the same digits appears later in the same digit-length range.
The familiar checkpoint example is the 3-member family \(345^3 = 41063625\), \(384^3 = 56623104\), and \(405^3 = 66430125\). All three cubes contain the same digits, merely in a different order. Problem 62 asks for the analogous phenomenon with family size \(5\), and then asks for the smallest cube inside that family.
The implementations do not compare cubes pairwise. Instead, they turn each cube into a canonical digit signature and group together all cubes with the same signature. The only subtle point is deciding when a group of size \(5\) is final rather than temporary.
Write
$$c(n)=n^3.$$
For any positive integer \(x\), define its digit signature by sorting its decimal digits:
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
Two integers are permutations of one another if and only if they have the same multiset of digits, and that is equivalent to having the same sorted digit string. Therefore two cubes belong to the same permutation family exactly when
$$\sigma(c(a))=\sigma(c(b)).$$
This converts the problem from “search among all digit permutations” into “group equal signatures together”.
Permuting digits preserves the number of digits, so a \(d\)-digit cube can only be paired with other \(d\)-digit cubes. That lets us split the search into independent buckets
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
Inside one bucket, define the signature class
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$$
Every valid family of cubic permutations is one of these classes. A rearrangement that would place a zero in front is irrelevant here, because it would no longer be a \(d\)-digit number and therefore would not lie in the same bucket.
Suppose \(d_0\) is the first digit length for which at least one class \(G_{d_0,s}\) has size \(5\). Any cube in a later bucket has more digits and is therefore numerically larger than every cube in bucket \(d_0\). So once bucket \(d_0\) is fully processed, the global answer must be the smallest cube among the size-5 classes inside that bucket.
This is the main invariant behind the streaming solution: we never need to keep data from older digit lengths after a bucket has been closed and checked.
A signature can hit count \(5\) partway through a bucket and later grow to \(6\). That would violate the word “exactly”. Therefore the correct stopping rule is:
Check a bucket only after all cubes with that digit length have been generated, and then accept those signature classes whose final size is exactly \(5\).
This explains why the implementations wait until the digit count changes before they inspect the accumulated groups.
The checkpoint family uses
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
All three cubes have the same signature
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
So within the 8-digit bucket there is a class \(G_{8,01234566}\) of size \(3\). The implementations use this known fact as a checkpoint: if the target family size is changed from \(5\) to \(3\), the returned cube must be \(41063625\), the smallest member of that class.
The C++, Python, and Java implementations iterate through \(n=1,2,3,\dots\), compute \(n^3\), measure its digit count, build the signature by sorting the decimal representation, and append the cube to the list stored under that signature. At any moment the map contains data only for the current digit-length bucket.
When the digit count increases, the previous bucket is complete. The implementation then scans all stored signature classes, keeps those whose final size equals the requested family size, and returns the smallest cube among them if any exist. If none exist, the map is cleared and the next bucket begins. The same code path works for the original target \(5\) and for the built-in checkpoint target \(3\).
If the search stops after testing roots up to \(N\), and the largest cube encountered has \(d\) decimal digits, then constructing one signature costs \(O(d \log d)\) because the implementations sort the digits. The map update is \(O(1)\) on average in the hash-based versions and \(O(\log S)\) in the ordered-map variant, where \(S\) is the number of active signatures in the current bucket.
Hence the total running time is \(O(N(d \log d + \log S))\) in the most conservative view, and effectively \(O(N d \log d)\) in the hash-based view. Memory usage is proportional to the current bucket: the implementations store one list of cubes per active signature, so the space requirement is \(O(B)\), where \(B\) is the number of cubes whose digit length matches the current bucket, and certainly \(O(N)\) in the worst case.
Gesucht ist der kleinste Kubus, für den genau fünf Permutationen seiner Dezimalziffern ebenfalls Kuben sind. Das Wort genau ist entscheidend: Eine Signatur mit fünf Treffern ist nur dann gültig, wenn innerhalb derselben Ziffernlänge kein sechster Kubus mit denselben Ziffern mehr auftaucht.
Das bekannte Kontrollbeispiel ist die 3er-Familie \(345^3 = 41063625\), \(384^3 = 56623104\) und \(405^3 = 66430125\). Diese drei Zahlen besitzen exakt dieselben Ziffern in anderer Reihenfolge. Problem 62 verlangt dasselbe Phänomen für Familiengröße \(5\) und dann den kleinsten Kubus dieser Familie.
Die Implementierungen vergleichen Kuben nicht paarweise. Stattdessen wird jeder Kubus auf eine kanonische Ziffernsignatur abgebildet, und alle Kuben mit derselben Signatur werden zusammengefasst. Die eigentliche Feinheit liegt darin, zu erkennen, wann eine Klasse der Größe \(5\) endgültig und nicht nur vorläufig ist.
Schreibe
$$c(n)=n^3.$$
Für jede positive ganze Zahl \(x\) definieren wir die Signatur durch Sortieren ihrer Dezimalziffern:
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
Zwei Zahlen sind genau dann Ziffernpermutationen voneinander, wenn sie dasselbe Ziffern-Multiset besitzen. Das ist äquivalent dazu, dass ihre sortierten Ziffernfolgen übereinstimmen. Für Kuben bedeutet das:
$$\sigma(c(a))=\sigma(c(b))$$
genau dann, wenn \(a^3\) und \(b^3\) in dieselbe Permutationsfamilie gehören.
Eine Ziffernpermutation erhält die Anzahl der Ziffern, daher kann ein \(d\)-stelliger Kubus nur mit anderen \(d\)-stelligen Kuben zusammengehören. Damit zerfällt die Suche in unabhängige Buckets
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
Innerhalb eines Buckets definieren wir für jede Signatur \(s\) die Klasse
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$$
Jede zulässige Familie kubischer Permutationen ist eine solche Klasse. Eine Umordnung mit führender Null spielt hier keine Rolle, weil sie keine \(d\)-stellige Zahl mehr wäre und damit den Bucket verlassen würde.
Sei \(d_0\) die erste Ziffernlänge, für die es mindestens eine Klasse \(G_{d_0,s}\) mit Größe \(5\) gibt. Jeder Kubus in einem späteren Bucket hat mehr Ziffern und ist deshalb größer als jeder Kubus im Bucket \(d_0\). Sobald Bucket \(d_0\) vollständig verarbeitet ist, muss die globale Lösung also der kleinste Kubus unter den 5er-Klassen dieses Buckets sein.
Genau dieses Invarianzargument trägt die Streaming-Lösung: Nach Abschluss eines Buckets muss man keine Daten älterer Ziffernlängen mehr behalten.
Eine Signatur kann mitten im Bucket zunächst auf \(5\) anwachsen und später noch einen sechsten Kubus bekommen. Dann wäre die Bedingung „genau fünf“ verletzt. Die korrekte Regel lautet daher:
Erst wenn alle Kuben dieser Ziffernlänge erzeugt wurden, prüft man, welche Signaturklassen in ihrer endgültigen Größe genau \(5\) Elemente besitzen.
Darum warten die Implementierungen bis zum Wechsel der Ziffernlänge, bevor sie die gesammelten Gruppen auswerten.
Die Kontrollfamilie besteht aus
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
Alle drei Kuben haben dieselbe Signatur
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
Im 8-stelligen Bucket existiert also eine Klasse \(G_{8,01234566}\) der Größe \(3\). Genau diese bekannte Tatsache wird als Kontrollpunkt benutzt: Wenn die Zielgröße von \(5\) auf \(3\) geändert wird, muss der zurückgegebene Kubus \(41063625\) sein, also das kleinste Element dieser Klasse.
Die C++-, Python- und Java-Implementierungen laufen über \(n=1,2,3,\dots\), berechnen \(n^3\), bestimmen die aktuelle Ziffernlänge, bilden die Signatur durch Sortieren der Dezimaldarstellung und hängen den Kubus an die Liste seiner Signatur an. Zu jedem Zeitpunkt enthält die Map nur Daten des aktuellen Ziffernlängen-Buckets.
Sobald die Ziffernlänge steigt, ist der vorige Bucket vollständig. Dann durchsucht die Implementierung alle gespeicherten Signaturklassen, wählt diejenigen mit endgültiger Größe gleich der gewünschten Familiengröße und gibt unter ihnen den kleinsten Kubus zurück, falls eine solche Klasse existiert. Andernfalls wird die Map geleert und der nächste Bucket beginnt. Derselbe Ablauf funktioniert sowohl für das Originalziel \(5\) als auch für den eingebauten Kontrollfall \(3\).
Wenn die Suche bis zu einer Wurzel \(N\) reicht und der größte dabei auftauchende Kubus \(d\) Dezimalziffern hat, kostet die Erzeugung einer Signatur \(O(d \log d)\), weil die Ziffern tatsächlich sortiert werden. Das Aktualisieren der Map kostet in den hashbasierten Varianten im Mittel \(O(1)\), in der geordneten Map-Variante \(O(\log S)\), wobei \(S\) die Anzahl aktiver Signaturen im aktuellen Bucket ist.
Damit erhält man konservativ eine Gesamtlaufzeit von \(O(N(d \log d + \log S))\); in der hashbasierten Sicht effektiv \(O(N d \log d)\). Der Speicherbedarf ist proportional zur aktuellen Bucket-Größe: Gespeichert wird pro aktiver Signatur eine Liste von Kuben, also \(O(B)\) für die Zahl \(B\) der Kuben in der laufenden Ziffernlänge und höchstens \(O(N)\) insgesamt.
Aranan değer, ondalık basamaklarının tam olarak beş permütasyonu da küp olan en küçük küptür. Buradaki kritik nokta tam olarak ifadesidir: bir imza beş küp üretse bile, aynı basamak uzunluğu içinde daha sonra altıncı bir küp geliyorsa o imza geçerli değildir.
Bilinen kontrol örneği 3 elemanlı ailedir: \(345^3 = 41063625\), \(384^3 = 56623104\) ve \(405^3 = 66430125\). Bu üç küp aynı basamak çoklu kümesine sahiptir; yalnızca sıraları farklıdır. Problem 62, aynı olgunun aile boyutu \(5\) için gerçekleştiği en küçük küpü sorar.
Uygulamalar küpleri ikili ikili karşılaştırmaz. Bunun yerine her küpü kanonik bir basamak imzasına dönüştürür ve aynı imzaya sahip küpleri aynı grupta toplar. Asıl incelik, boyutu \(5\) olan bir grubun geçici değil kesin olduğuna ne zaman karar verileceğidir.
Şöyle yazalım:
$$c(n)=n^3.$$
Her pozitif tam sayı \(x\) için, ondalık basamakları sıralayarak bir imza tanımlayalım:
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
İki sayı ancak ve ancak aynı basamak çoklu kümesine sahipse birbirinin permütasyonudur; bu da sıralanmış basamak dizilerinin eşit olmasıyla aynıdır. Dolayısıyla iki küpün aynı ailede olması için ve ancak bunun için
$$\sigma(c(a))=\sigma(c(b))$$
gerekir. Böylece problem, “tüm permütasyonları üret” biçiminden çıkıp “aynı imzaları grupla” biçimine dönüşür.
Basamak permütasyonu, basamak sayısını korur. O halde \(d\) basamaklı bir küp ancak başka \(d\) basamaklı küplerle aynı ailede olabilir. Bu nedenle aramayı bağımsız kovalar halinde ayırabiliriz:
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
Belirli bir \(d\) için ve imza \(s\) altında sınıfı
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}$$
olarak tanımlayalım. Geçerli her kübik permütasyon ailesi bu sınıflardan biridir. Başta sıfır bulunan bir yeniden düzenleme burada sayılmaz; çünkü o zaman sayı artık \(d\) basamaklı olmaz ve aynı kovada yer almaz.
Diyelim ki boyutu \(5\) olan en az bir sınıfın ilk kez ortaya çıktığı basamak uzunluğu \(d_0\) olsun. Daha sonraki her kovadaki küp daha fazla basamaklıdır; dolayısıyla sayısal olarak da \(d_0\) kovasındaki tüm küplerden büyüktür. Bu yüzden \(d_0\) kovası tamamen işlendiği anda, genel cevabın o kovadaki boyutu \(5\) olan sınıfların en küçük elemanlarından biri olduğu kesinleşir.
Akış halinde çalışan çözümün temel değişmezi tam olarak budur: bir kova kapatılıp denetlendikten sonra daha eski basamak uzunluklarından veri tutmaya gerek kalmaz.
Bir imza kovanın ortasında geçici olarak \(5\) elemana ulaşabilir, fakat aynı basamak uzunluğu içinde daha sonra altıncı bir küp de gelebilir. Böyle bir durumda “tam olarak beş” şartı bozulur. Doğru durma kuralı şudur:
Ancak o basamak uzunluğundaki bütün küpler üretildikten sonra, nihai boyutu tam olarak \(5\) olan imza sınıfları kabul edilir.
Uygulamaların basamak sayısı değişene kadar bekleyip daha sonra grupları taramasının nedeni budur.
Kontrol ailesi şu küplerden oluşur:
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
Bu üç küpün imzası aynıdır:
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
Yani 8 basamaklı kovada boyutu \(3\) olan bir \(G_{8,01234566}\) sınıfı vardır. Uygulamalar bunu kontrol noktası olarak kullanır: hedef aile boyutu \(5\) yerine \(3\) yapılırsa dönen küp \(41063625\) olmalıdır; çünkü bu, o sınıfın en küçük elemanıdır.
C++, Python ve Java uygulamaları \(n=1,2,3,\dots\) üzerinden ilerler, \(n^3\)'ü hesaplar, basamak sayısını bulur, ondalık yazımı sıralayarak imzayı üretir ve o imza için tutulan listeye küpü ekler. Her anda harita yalnızca o anki basamak uzunluğuna ait verileri taşır.
Basamak sayısı arttığında önceki kova tamamlanmış olur. Uygulama bu anda biriken tüm imza sınıflarını tarar, nihai boyutu istenen aile boyutuna eşit olanları seçer ve varsa bunların içindeki en küçük küpü döndürür. Uygun sınıf yoksa harita temizlenir ve bir sonraki kova başlar. Aynı mekanizma hem özgün hedef \(5\) hem de yerleşik kontrol hedefi \(3\) için çalışır.
Arama en fazla \(N\) köküne kadar gidiyor ve karşılaşılan en büyük küp \(d\) ondalık basamak içeriyorsa, tek bir imza oluşturmanın maliyeti \(O(d \log d)\) olur; çünkü uygulamalar basamakları gerçekten sıralar. Harita güncellemesi, karma tabanlı sürümlerde ortalama \(O(1)\), sıralı-harita sürümünde ise \(O(\log S)\) maliyetlidir; burada \(S\), aktif kovadaki imza sayısıdır.
Buna göre toplam süre en temkinli ifadeyle \(O(N(d \log d + \log S))\), karma harita bakışında fiilen \(O(N d \log d)\) olur. Bellek kullanımı mevcut kovayla orantılıdır: her aktif imza için bir küp listesi tutulduğu için alan gereksinimi o kovadaki küp sayısı \(B\) ile \(O(B)\), en kötü durumda ise \(O(N)\)'dir.
Buscamos el cubo más pequeño tal que exactamente cinco permutaciones de sus dígitos decimales también sean cubos. La palabra exactamente es esencial: una firma que llegue a cinco cubos solo es válida si dentro del mismo bloque de longitud decimal no aparece más tarde un sexto cubo con los mismos dígitos.
El ejemplo de control conocido es la familia de tamaño 3 formada por \(345^3 = 41063625\), \(384^3 = 56623104\) y \(405^3 = 66430125\). Los tres cubos contienen el mismo multiconjunto de dígitos en distinto orden. El problema 62 pide el análogo para tamaño \(5\) y, dentro de esa familia, el cubo más pequeño.
Las implementaciones no comparan cubos por pares. En su lugar, convierten cada cubo en una firma canónica de dígitos y agrupan juntos todos los cubos con la misma firma. La parte delicada consiste en decidir cuándo un grupo de tamaño \(5\) ya es definitivo y no provisional.
Escribimos
$$c(n)=n^3.$$
Para cada entero positivo \(x\), definimos su firma ordenando sus dígitos decimales:
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
Dos enteros son permutaciones uno del otro si y solo si contienen los mismos dígitos con las mismas multiplicidades. Eso equivale a que sus cadenas ordenadas coincidan. Por tanto, dos cubos pertenecen a la misma familia exactamente cuando
$$\sigma(c(a))=\sigma(c(b)).$$
Así el problema deja de ser “probar muchas permutaciones” y pasa a ser “agrupar firmas iguales”.
Una permutación de dígitos conserva la cantidad de dígitos, de modo que un cubo de \(d\) cifras solo puede emparejarse con otros cubos de \(d\) cifras. Esto permite dividir la búsqueda en bloques independientes
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
Dentro de un bloque, para cada firma \(s\) definimos
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$$
Toda familia válida de permutaciones cúbicas es una clase de este tipo. Si una reordenación colocara un cero al frente, ya no sería un número de \(d\) cifras y por tanto quedaría fuera del mismo bloque.
Sea \(d_0\) la primera longitud decimal para la que existe alguna clase \(G_{d_0,s}\) de tamaño \(5\). Todo cubo de un bloque posterior tiene más dígitos y, por lo tanto, es mayor que cualquier cubo del bloque \(d_0\). En consecuencia, una vez procesado por completo el bloque \(d_0\), la respuesta global tiene que ser el menor cubo entre las clases de tamaño \(5\) de ese bloque.
Ese es el invariante central de la solución en flujo: después de cerrar y revisar un bloque, ya no hace falta conservar datos de longitudes anteriores.
Una firma puede alcanzar el valor \(5\) a mitad de un bloque y luego crecer a \(6\) cuando aparece otro cubo con la misma cantidad de dígitos. Eso rompería la condición de “exactamente cinco”. Por eso la regla correcta es:
solo después de generar todos los cubos de una longitud decimal dada se aceptan las clases cuya cardinalidad final es exactamente \(5\).
Esta es la razón por la que las implementaciones esperan al cambio de longitud antes de inspeccionar los grupos acumulados.
La familia de control es
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
Los tres cubos tienen la misma firma
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
Así, dentro del bloque de 8 cifras aparece una clase \(G_{8,01234566}\) de tamaño \(3\). Las implementaciones usan este hecho como verificación: si el tamaño objetivo cambia de \(5\) a \(3\), el cubo devuelto debe ser \(41063625\), el menor elemento de esa clase.
Las implementaciones en C++, Python y Java recorren \(n=1,2,3,\dots\), calculan \(n^3\), obtienen su número de cifras, construyen la firma ordenando la representación decimal y añaden el cubo a la lista asociada con esa firma. En todo momento el mapa solo contiene datos del bloque actual.
Cuando aumenta el número de cifras, el bloque anterior ya está completo. Entonces la implementación recorre todas las clases almacenadas, conserva aquellas cuya talla final coincide con la familia pedida y, si existe alguna, devuelve el cubo más pequeño entre ellas. Si no existe, vacía el mapa y empieza el siguiente bloque. El mismo esquema sirve tanto para el objetivo original \(5\) como para la comprobación interna de tamaño \(3\).
Si la búsqueda se detiene tras probar raíces hasta \(N\), y el mayor cubo encontrado tiene \(d\) cifras decimales, construir una firma cuesta \(O(d \log d)\) porque las implementaciones ordenan realmente los dígitos. La actualización del mapa cuesta \(O(1)\) en promedio en las versiones basadas en hash y \(O(\log S)\) en la variante con mapa ordenado, donde \(S\) es el número de firmas activas en el bloque actual.
Por tanto, el tiempo total es \(O(N(d \log d + \log S))\) en la cota más conservadora, y de forma efectiva \(O(N d \log d)\) en la visión basada en hash. El uso de memoria es proporcional al bloque actual: como se guarda una lista de cubos por firma activa, el espacio es \(O(B)\), donde \(B\) es el número de cubos en el bloque de longitud actual, y desde luego \(O(N)\) en el peor caso.
题目要求找出这样一个最小立方数：它的十进制数字恰好有五个排列也仍然是立方数。这里“恰好”非常关键。某个数字签名暂时出现了 5 个立方数，并不立刻说明它有效；如果在同一位数范围内稍后又出现第 6 个，那么这个签名就不满足题意。
已知的检验例子是 3 个成员的家族： \(345^3 = 41063625\)、\(384^3 = 56623104\)、\(405^3 = 66430125\)。这三个立方数的数字完全相同，只是顺序不同。第 62 题要求找到对应的 5 成员家族，并返回其中最小的那个立方数。
实现并不会把立方数两两比较，而是先把每个立方数压缩成一个“规范数字签名”，然后把签名相同的立方数归入同一组。真正需要解释清楚的是：为什么必须等到同一位数区间全部处理完，才能判断某一组是否真的大小为 \(5\)。
记
$$c(n)=n^3.$$
对任意正整数 \(x\)，把它的十进制数字排序，定义签名
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
两个整数互为数字排列，当且仅当它们含有完全相同的数字多重集；这与“排序后的数字串相同”完全等价。因此两个立方数属于同一排列家族，当且仅当
$$\sigma(c(a))=\sigma(c(b)).$$
这样一来，题目就从“显式尝试各种排列”变成了“把相同签名的立方数分组”。
数字重排不会改变位数，所以一个 \(d\) 位立方数只能和其他 \(d\) 位立方数配对。于是搜索可以拆成彼此独立的位数桶：
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
在固定的位数 \(d\) 内，对每个签名 \(s\) 定义类
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$$
所有合法的立方排列家族都恰好是这些类中的某一个。某些重排如果把 \(0\) 放到最前面，就会变成更短的数；这种情况不会留在同一个 \(d\) 位桶中，因此不会影响分桶结论。
设 \(d_0\) 是第一次出现大小为 \(5\) 的某个类 \(G_{d_0,s}\) 的位数。任何更后面的桶都包含更多位数的立方数，因此其中每个数都严格大于 \(d_0\) 桶中的任意立方数。于是只要 \(d_0\) 这个桶已经完整处理完，最终答案就一定是这个桶里所有大小为 \(5\) 的类中最小的立方数。
这就是流式算法的核心不变量：某一位数桶一旦“封口”并检查完毕，就再也不需要保留更早桶的数据。
某个签名在桶的中途达到 \(5\)，并不意味着它的最终大小就是 \(5\)。稍后仍可能出现同位数、同签名的第 6 个立方数，从而把它变成大小 \(6\) 的类。题目要求的是“恰好 5 个”，所以正确的停止条件是：
必须先把这一位数的所有立方数全部生成完，再检查哪些签名类的最终大小恰好等于 \(5\)。
这正是实现中“等位数变化后再统一扫描当前分组”的原因。
检验家族是
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
它们有完全相同的签名
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
因此在 8 位数桶中，存在一个大小为 \(3\) 的类 \(G_{8,01234566}\)。实现利用这一事实做自检：如果把目标家族大小从 \(5\) 改成 \(3\)，返回值就必须是该类中最小的成员 \(41063625\)。
C++、Python 和 Java 实现都按 \(n=1,2,3,\dots\) 顺序推进，计算 \(n^3\)，求出它的位数，把十进制表示排序成签名，然后把这个立方数追加到对应签名的列表中。任意时刻，映射里只保存当前位数桶的数据。
当位数增加时，前一个桶就已经完整。此时实现会遍历当前保存的所有签名类，挑出最终大小等于目标家族大小的那些类；如果存在，就返回其中最小的立方数；如果不存在，就清空映射并开始下一个桶。原题的目标值 \(5\) 和内置检验值 \(3\) 共享完全相同的流程。
如果搜索在根 \(N\) 处停止，而遇到的最大立方数有 \(d\) 位十进制数字，那么构造一次签名的代价是 \(O(d \log d)\)，因为实现确实对数字字符做排序。映射更新在基于哈希的版本中平均为 \(O(1)\)，在有序映射版本中为 \(O(\log S)\)，其中 \(S\) 是当前桶中活跃签名的数量。
因此，总时间复杂度在最保守的写法下是 \(O(N(d \log d + \log S))\)；若按哈希映射来理解，则可视为 \(O(N d \log d)\)。空间复杂度与当前桶成正比：实现为每个活跃签名保留一个立方数列表，所以空间为 \(O(B)\)，其中 \(B\) 是当前位数桶中的立方数个数；从最坏情况看当然也不超过 \(O(N)\)。
Нужно найти наименьший куб, для которого ровно пять перестановок его десятичных цифр тоже являются кубами. Слово ровно здесь принципиально: если некоторый шаблон цифр сначала дал пять кубов, но позже в том же диапазоне длины числа появился шестой, такой шаблон уже не подходит.
Известный контрольный пример даёт семейство размера 3: \(345^3 = 41063625\), \(384^3 = 56623104\) и \(405^3 = 66430125\). Эти кубы состоят из одних и тех же цифр в разном порядке. В задаче 62 требуется найти аналогичное семейство размера \(5\) и вернуть наименьший куб внутри него.
Реализации не сравнивают кубы попарно. Вместо этого каждый куб переводится в каноническую цифровую сигнатуру, а затем кубы с одинаковой сигнатурой группируются вместе. Главная тонкость состоит в том, что класс размера \(5\) нельзя принимать сразу: сначала нужно убедиться, что его окончательный размер в данном разряде действительно равен \(5\).
Обозначим
$$c(n)=n^3.$$
Для любого положительного целого \(x\) определим сигнатуру как отсортированную запись его десятичных цифр:
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
Два числа являются перестановками друг друга тогда и только тогда, когда у них совпадает мультимножество цифр. Это эквивалентно совпадению отсортированных строк цифр. Следовательно, два куба лежат в одном семействе тогда и только тогда, когда
$$\sigma(c(a))=\sigma(c(b)).$$
Так задача превращается из перебора перестановок в задачу группировки по одинаковым сигнатурам.
Перестановка цифр сохраняет количество цифр, поэтому \(d\)-значный куб может сочетаться только с другими \(d\)-значными кубами. Это позволяет разбить поиск на независимые корзины
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
Внутри такой корзины для сигнатуры \(s\) введём класс
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$$
Каждое допустимое семейство кубических перестановок является одним из таких классов. Перестановка с ведущим нулём здесь не мешает: она уже не будет \(d\)-значным числом и выйдет из рассматриваемой корзины.
Пусть \(d_0\) — первая длина записи, при которой существует хотя бы один класс \(G_{d_0,s}\) размера \(5\). Любой куб из более поздней корзины имеет больше цифр и потому строго больше любого куба из корзины \(d_0\). Значит, после полного завершения корзины \(d_0\) глобальный ответ обязан быть наименьшим кубом среди всех её классов размера \(5\).
Это и есть главный инвариант потокового решения: как только корзина закрыта и проверена, данные о более ранних длинах больше не нужны.
Некоторая сигнатура может достигнуть значения \(5\) в середине корзины, а потом вырасти до \(6\), когда встретится ещё один куб той же длины. Тогда условие «ровно пять» нарушится. Поэтому правильное правило остановки такое:
сначала нужно полностью сгенерировать все кубы данной длины, и только потом принимать те сигнатурные классы, у которых окончательный размер равен \(5\).
Именно поэтому реализации ждут смены числа цифр, а уже затем просматривают накопленные группы.
Контрольное семейство состоит из
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
У всех трёх кубов одна и та же сигнатура
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
Следовательно, в корзине 8-значных чисел существует класс \(G_{8,01234566}\) размера \(3\). Этот факт используется как проверка: если изменить целевой размер семейства с \(5\) на \(3\), реализация обязана вернуть \(41063625\), то есть наименьший элемент этого класса.
Реализации на C++, Python и Java перебирают \(n=1,2,3,\dots\), вычисляют \(n^3\), определяют число цифр, строят сигнатуру сортировкой десятичной записи и добавляют куб в список по соответствующему ключу. В любой момент отображение содержит данные только для текущей корзины по длине записи.
Когда число цифр увеличивается, предыдущая корзина завершена. Тогда реализация просматривает все накопленные сигнатурные классы, выбирает те, чей окончательный размер равен требуемому размеру семейства, и возвращает наименьший куб среди них, если такие классы есть. Иначе структура очищается, и начинается следующая корзина. Один и тот же механизм работает и для исходной цели \(5\), и для встроенной контрольной цели \(3\).
Если поиск заканчивается после проверки корней до \(N\), а наибольший встретившийся куб имеет \(d\) десятичных цифр, то построение одной сигнатуры стоит \(O(d \log d)\), поскольку цифры действительно сортируются. Обновление отображения стоит в среднем \(O(1)\) в hash-вариантах и \(O(\log S)\) в варианте с упорядоченной картой, где \(S\) — число активных сигнатур в текущей корзине.
Следовательно, общее время можно оценить как \(O(N(d \log d + \log S))\) в наиболее осторожной формулировке, а в hash-модели практически как \(O(N d \log d)\). Память пропорциональна текущей корзине: хранится один список кубов на каждую активную сигнатуру, то есть \(O(B)\), где \(B\) — число кубов в текущем диапазоне длины, и, конечно, не хуже \(O(N)\) в худшем случае.
المطلوب هو إيجاد أصغر مكعب تكون بالضبط خمسة تبديلات لأرقامه العشرية مكعبات أيضًا. كلمة بالضبط هي النقطة الحاسمة هنا: قد تصل مجموعة رقمية ما إلى خمسة مكعبات مؤقتًا، لكن إذا ظهر لاحقًا مكعب سادس بالأرقام نفسها داخل نفس نطاق عدد الخانات، فإن هذه المجموعة لا تحقق الشرط.
مثال التحقق المعروف هو العائلة ذات الحجم 3: \(345^3 = 41063625\)، و\(384^3 = 56623104\)، و\(405^3 = 66430125\). هذه المكعبات الثلاثة تملك الأرقام نفسها بترتيبات مختلفة. مسألة 62 تطلب النسخة المقابلة عندما يكون حجم العائلة \(5\)، ثم تطلب أصغر مكعب داخل تلك العائلة.
التنفيذات لا تقارن المكعبات زوجيًا. بدلًا من ذلك، يحول كل مكعب إلى توقيع رقمي قانوني، ثم يجمع كل المكعبات التي تشترك في التوقيع نفسه. الصعوبة الحقيقية هي تحديد اللحظة التي يصبح فيها حجم المجموعة \(5\) نهائيًا لا مؤقتًا.
نكتب
$$c(n)=n^3.$$
ولكل عدد صحيح موجب \(x\)، نعرّف توقيعه بترتيب أرقامه العشرية:
$$\sigma(x)=\operatorname{sort}(\text{digits}(x)).$$
يكون عددان تبديلين لبعضهما إذا وفقط إذا امتلكا نفس متعدد الأرقام. وهذا يكافئ تمامًا تساوي السلسلتين المرتبتين للأرقام. لذلك ينتمي مكعبان إلى العائلة نفسها إذا وفقط إذا
$$\sigma(c(a))=\sigma(c(b)).$$
وهكذا تنتقل المسألة من “تجربة جميع التبديلات” إلى “تجميع المفاتيح المتطابقة”.
تبديل الأرقام لا يغير عدد الخانات، لذلك لا يمكن لمكعب ذي \(d\) خانات أن ينتمي إلا مع مكعبات أخرى ذات \(d\) خانات. لهذا يمكن تقسيم البحث إلى سلال مستقلة:
$$B_d=\{n\ge 1: 10^{d-1}\le n^3\lt 10^d\}.$$
وداخل السلة ذاتها، ولأي توقيع \(s\)، نعرّف الفئة
$$G_{d,s}=\{n^3 : n\in B_d,\ \sigma(n^3)=s\}.$$
كل عائلة صحيحة من المكعبات المتبادلة هي إحدى هذه الفئات. وإذا أدى ترتيب ما إلى وضع الصفر في البداية، فلن يبقى العدد ذا \(d\) خانات، وبالتالي لن يظل داخل السلة نفسها.
لنفترض أن \(d_0\) هو أول عدد خانات تظهر عنده فئة واحدة على الأقل \(G_{d_0,s}\) بحجم \(5\). أي مكعب في سلة لاحقة يملك خانات أكثر، ولذلك فهو أكبر عددًا من أي مكعب في سلة \(d_0\). إذن ما إن تكتمل معالجة سلة \(d_0\)، يصبح الجواب النهائي هو أصغر مكعب بين جميع الفئات ذات الحجم \(5\) داخل هذه السلة.
هذه هي الفكرة الثابتة الأساسية وراء الحل المتدفق: بعد إغلاق سلة معينة وفحصها، لا تعود هناك حاجة للاحتفاظ ببيانات السلال الأقدم.
قد يصل توقيع ما إلى العدد \(5\) في منتصف السلة، ثم يظهر لاحقًا مكعب سادس له التوقيع نفسه وعدد الخانات نفسه. عندها يختفي شرط “بالضبط خمسة”. لذلك تكون قاعدة التوقف الصحيحة كما يلي:
لا نقبل أي فئة إلا بعد توليد جميع المكعبات ذات عدد الخانات الحالي، ثم نختار الفئات التي يساوي حجمها النهائي تمامًا \(5\).
ولهذا السبب تحديدًا تنتظر التنفيذات حتى يتغير عدد الخانات قبل أن تفحص المجموعات المتراكمة.
عائلة التحقق هي
$$345^3=41063625,\qquad 384^3=56623104,\qquad 405^3=66430125.$$
وجميع هذه المكعبات تشترك في التوقيع نفسه
$$\sigma(41063625)=\sigma(56623104)=\sigma(66430125)=01234566.$$
إذن توجد داخل سلة الأعداد ذات 8 خانات فئة \(G_{8,01234566}\) بحجم \(3\). وتستعمل التنفيذات هذه الحقيقة كاختبار صحة: إذا تغير الحجم المطلوب من \(5\) إلى \(3\)، فيجب أن يكون الناتج هو \(41063625\)، أي أصغر عنصر في تلك الفئة.
تسير تنفيذات C++ وPython وJava على \(n=1,2,3,\dots\)، وتحسب \(n^3\)، ثم تحدد عدد خاناته، وتبني التوقيع بترتيب التمثيل العشري، ثم تضيف المكعب إلى القائمة المقابلة لذلك التوقيع. وفي كل لحظة لا يحتوي القاموس إلا على بيانات السلة الحالية فقط.
عندما يزداد عدد الخانات، فهذا يعني أن السلة السابقة اكتملت. عندها تفحص التنفيذات جميع فئات التواقيع المخزنة، وتختار الفئات التي يساوي حجمها النهائي حجم العائلة المطلوب، ثم تعيد أصغر مكعب بينها إن وُجد. وإذا لم توجد أي فئة مناسبة، يُمسح القاموس وتبدأ السلة التالية. المسار نفسه يعمل للهدف الأصلي \(5\) ولحالة التحقق الداخلية \(3\).
إذا توقف البحث بعد اختبار الجذور حتى \(N\)، وكان أكبر مكعب تمت رؤيته يملك \(d\) خانات عشرية، فإن بناء توقيع واحد يكلف \(O(d \log d)\) لأن التنفيذات ترتب الأرقام فعليًا. أما تحديث القاموس فيكلف في المتوسط \(O(1)\) في النسخ المعتمدة على التجزئة، و\(O(\log S)\) في النسخة التي تستعمل خريطة مرتبة، حيث \(S\) هو عدد التواقيع النشطة في السلة الحالية.
وبالتالي يمكن كتابة الزمن الكلي على الصورة \(O(N(d \log d + \log S))\) في التقدير الأكثر تحفظًا، ويصبح عمليًا \(O(N d \log d)\) عند النظر إلى النسخ المعتمدة على التجزئة. أما الذاكرة فهي متناسبة مع السلة الحالية: إذ تُخزن قائمة مكعبات لكل توقيع نشط، ولذلك تكون \(O(B)\)، حيث \(B\) هو عدد المكعبات في سلة عدد الخانات الحالية، وبالطبع لا تتجاوز \(O(N)\) في أسوأ الأحوال.