<< problem 61 - Cyclical figurate numbers | Powerful digit counts - problem 63 >> |

# 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:

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

Output:

*(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 |

<< problem 61 - Cyclical figurate numbers | Powerful digit counts - problem 63 >> |