Project Euler Problem 62 Solution: Cubic Permutations

Project Euler Problem 62 Statement

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution

Grouping by Permutations: By sorting the digits of each cube and using the sorted string as a key in the cubes dictionary, the script effectively groups all cubes that are permutations of each other. This groups cubes that are digit permutations of one another.

Filtering by Exact Count (K): The script looks for groups that contain exactly K cubes. For Project Euler Problem 62, K is 5, meaning we're interested in the first cube for which exactly five permutations of its digits are also cubes.

Identifying the Smallest Cube: By selecting the first cube (cp[0]) in each qualifying group and sorting these, the script ensures that the smallest such cube is identified and printed.

A look at some of the (arbitrary) indexes and values of cube[] with K=5, N=10000

cube = [
...
'0000122779':   [1009027027, 1092727000], # 1003^3, 1030^3
'0000001133':   [1003003001, 1030301000, 1331000000], # 1001^3, 1010^3, 1100^3
'0000011268':   [1006012008, 1061208000, 8012006001, 8120601000], # 1002^3, 1020^3, 2001^3, 2010^3
'012334556789': [127035954683, 352045367981, 373559126408, 569310543872, 589323567104] # 5027^3, 7061^3, 7202^3, 8288^3, 8384^3 
... ]

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 62

HackerRank Project Euler 62: You are given $N$, find the smallest cube for which exactly $K$, $3\le K\le 49$ permutations of its digits are cube of some number which is $(\lt N, 1000\le N\le 10^6)$. If there are multiple sets, print the minimal element of each in sorted order.

Python Source Code

from collections import defaultdict
cubes = defaultdict(list)
N, K = map(int, input().split())

for n in range(100, N):
    cube = n*n*n
    digits = ''.join(sorted(str(cube)))
    cubes[digits].append(cube)

for x in sorted([cp[0] for cp in cubes.values() if len(cp)==K]):
    print(x)