### Cubic permutations题号：62 难度： 15 中英对照

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.

### Code

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public final class p62 {

public static void main(String[] args) {
long start = System.nanoTime();
BigInteger result = run();
long end = System.nanoTime();
System.out.println( result );
System.out.println (( end - start )/1000000 +"ms");
}

//从0开始遍历，求每个数字的立方，并加入到相应的“立方数类别”中，若有个立方数类别有5个元素，则返回其中的最小值。
public static BigInteger run() {
int numDigits = 0;
Map<String,Integer> lowest = new HashMap<>();   //记录同属于一个“立方数类别”的数中的最小值
Map<String,Integer> counts = new HashMap<>();   //记录同属于一个“立方数类别”的数的个数
for (int i = 0; ; i++) {
String numClass = getCubeNumberClass(i);
//如果当前数的立方值的位数，达到新值时，才对counts中的数目进行判断，减少判断的次数
if (numClass.length() > numDigits) {
int min = Integer.MAX_VALUE;  //答案的上限，设置为2147483647
for (String nc : counts.keySet()) {
if (counts.get(nc) == 5)
min = Math.min(lowest.get(nc), min);
}
if (min != Integer.MAX_VALUE)
return cube(min);

lowest.clear();
counts.clear();
numDigits = numClass.length();
}

if (!lowest.containsKey(numClass)) {
lowest.put(numClass, i);
counts.put(numClass, 0);
}
counts.put(numClass, counts.get(numClass) + 1);
}
}

//对立方数的各个位进行排序，作为类别。如立方数排序后一样的，认为是同一类
private static String getCubeNumberClass(int x) {
char[] digits = cube(x).toString().toCharArray();
Arrays.sort(digits);
return new String(digits);
}

//获得立方数
private static BigInteger cube(int x) {
return BigInteger.valueOf(x).pow(3);
}

}
127035954683
54ms