Problem 62: Cubic permutations

(see projecteuler.net/problem=62)

The cube, 41063625 (345^3), can be permuted to produce two other cubes: 56623104 (384^3) and 66430125 (405^3).
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.

Algorithm

A function fingerprint was already used in problem 49 and problem 52: if fingerprint(a) == fingerprint(b) then a is a permutation of b.

Step 1 of my program computes all cubes from 1^3 to maxCube^3and stores them indexed by their fingerprint (see matches).

Step 2 goes through all fingerprints with the specified number of permutations and transfers each fingerprint's first cube (the "smallest") to an std::set called smallest.

Finally, smallest^3 is printed - using the fact that each std::set is automatically sorted (needed for the Hackerrank version of the problem).

Modifications by HackerRank

The modified problem requires all permutations to be below maxCube^3.
When running the problem with the official solution (parameter xyz 5 where xyz is the solution) then it will fail to find the correct solution.

The reason is that all but the initial permutations of maxCube^3 are bigger than maxCube^3.
Therefore the solution is only found if all cubes are processed which produce the solution and all bigger cubes that have still the same number of digits.
To be safe, the parameter should be solution * {^3}sqrt{10} approx solution * 2.16.

My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <map>
#include <set>
#include <vector>
#include <iostream>
 
// count how often each digit occurs,
// store zero at lowest position, then ones, etc.
// e.g. 5063 means 3 zeros, 6 ones, no twos, 5 threes and nothing else
// note: can't handle input values with 2^6 or more identical digits
unsigned long long fingerprint(unsigned long long x)
{
unsigned long long result = 0;
while (x > 0)
{
// extract lowest digit
auto digit = x % 10;
x /= 10;
 
// subdivide 64 bit integer into 10 "digit counters", each 6 bits wide
// => each digit may occur up to 2^6=64 times, more than enough ...
const auto BitsPerDigit = 6;
result += 1ULL << (BitsPerDigit * digit);
}
return result;
}
 
int main()
{
unsigned int maxCube = 10000;
unsigned int numPermutations = 5;
std::cin >> maxCube >> numPermutations;
 
// [fingerprint] => [list of numbers, where number^3 produced that fingerprint]
std::map<unsigned long long, std::vector<unsigned int>> matches;
for (unsigned int i = 1; i < maxCube; i++)
{
// find fingerprint
auto cube = (unsigned long long)i * i * i;
// add current number to the fingerprint's list
matches[fingerprint(cube)].push_back(i);
}
 
// extract all smallest cube, std::set is sorting them
std::set<unsigned long long> smallest;
for (auto m : matches)
// right number of permutations ?
if (m.second.size() == numPermutations)
smallest.insert(m.second.front());
 
// print in ascending order
for (auto s : smallest)
std::cout << (s*s*s) << std::endl;
 
return 0;
}

This solution contains 7 empty lines, 13 comments and 4 preprocessor commands.

Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

Input data (separated by spaces or newlines):

This is equivalent to
echo "1000 3" | ./62

Output:

(please click 'Go !')

(this interactive test is still under development, computations will be aborted after one second)

Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 3 MByte.

(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL)

See here for a comparison of all solutions.

Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL.

Changelog

March 1, 2017 submitted solution
April 22, 2017 added comments

Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler062

My code solved 10 out of 10 test cases (score: 100%)

Difficulty

Project Euler ranks this problem at 15% (out of 100%).

Hackerrank describes this problem as easy.

Note:
Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is never an option.

Links

projecteuler.net/thread=62 - the best forum on the subject (note: you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-62-cube-five-permutations/ (written by Kristian Edlund)
Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p062.java (written by Nayuki)
Go: github.com/frrad/project-euler/blob/master/golang/Problem062.go (written by Frederick Robinson)
Scala: github.com/samskivert/euler-scala/blob/master/Euler062.scala (written by Michael Bayne)

Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.
yellow problems score less than 100% at Hackerrank (but still solve the original problem).
gray problems are already solved but I haven't published my solution yet.
blue problems are already solved and there wasn't a Hackerrank version of it (at the time I solved it) or I didn't care about it because it differed too much.

Please click on a problem's number to open my solution to that problem:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
The 133 solved problems had an average difficulty of 16.9% at Project Euler and I scored 11,174 points (out of 12300) at Hackerrank's Project Euler+.
more about me can be found on my homepage.
some names mentioned on this site may be trademarks of their respective owners.
thanks to the KaTeX team for their great typesetting library !