Project Euler/62: Difference between revisions
From charlesreid1
(→Code) |
|||
| Line 6: | Line 6: | ||
==Solution Technique== | ==Solution Technique== | ||
We are looking for the smallest cube that permutes with N other cubes. | |||
The key idea here is that, for a particular cube permuting to other cubes, the cubes must all have the same number of digits - which provides a lower and upper bound on the numbers that need to be examined for a particular cube. This means we can break the problems into chunks, each increasing in size by an order of magnitude, and tackle the problem that way. (For reference, the final result is 12 digits!) | |||
The core data structure to do this task quickly is the hash map - we proceed by computing a round of <math>10^{N-1}</math> to <math>10^{N}</math> perfect cubes, and sort their digits. These form the hash map keys, and we store the cube that results in a list so that we can cross-reference it in our search for permuted digits. | |||
==Code== | ==Code== | ||
Revision as of 10:25, 8 January 2018
Problem Statement
Cubes that permute to other cubes: find the smallest cube for which exactly 5 permutations of the cube are also cubes.
Link: https://projecteuler.net/problem=62
Solution Technique
We are looking for the smallest cube that permutes with N other cubes.
The key idea here is that, for a particular cube permuting to other cubes, the cubes must all have the same number of digits - which provides a lower and upper bound on the numbers that need to be examined for a particular cube. This means we can break the problems into chunks, each increasing in size by an order of magnitude, and tackle the problem that way. (For reference, the final result is 12 digits!)
The core data structure to do this task quickly is the hash map - we proceed by computing a round of $ 10^{N-1} $ to $ 10^{N} $ perfect cubes, and sort their digits. These form the hash map keys, and we store the cube that results in a list so that we can cross-reference it in our search for permuted digits.
Code
https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/062/Problem062.java
Flags
