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 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)	``````

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.