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

A simple approach

Using the function prime_sieve(N), introduced in Project Euler Problem 7, to find prime numbers less than N, we can solve this problem in less than 100ms using a couple lines of Python:

At the end of the main loop the list is ready to accept as many queries as required.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 62

HackerRank Project Euler 65 raises the limit to 30,000 from 100. This solution works for both.

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)

Run Project Euler Problem 62 using Python on repl.it.

Last Word

The sum, s, and the list, primeSum[], have been preset with the first prime number 2 so we could just loop through odd numbers.
Have a look at the prime_sieve() function listed in Common Functions and Routines for Project Euler.