Project Euler Problem 62 Solution

Project Euler Problem 62 Solution

Cubic permutations

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 62 Statement

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). 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

HackerRank Project Euler 62 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)	

Last Word