(Project Euler #62)The digits of 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.Here is my code which properly works and prints the number of permutations which are cube for a particular i. I have found numbers which have 1,2,3 permutations as perfect cubes. Here is the output which checked from i=0 to i=999 in around 120~130 seconds and found no such number. I need to increase the efficiency of the code otherwise searching will take a very long time. With increase in i the number of digits in cube of i increases and total permutations increase rapidly, hence a rapid decrease in speed.It also prints 345,3 (correct) and none of 384 or 405 (good).boolean[] checked = new boolean[999];    Arrays.fill(checked, false);    for (int i = 1; i < 999; i++) {        if (!checked[i]) {                          int cube_perms = 0;            long i_3 = i * i * i;            int len = String.valueOf(i_3).length();            ArrayList<int[]> perms = getPermutations(longToArray(i_3));            for (int[] x : perms) {                int num = arrayToInt(x);                if (String.valueOf(num).length() < len) {                    continue;                }                int cubrt = (int) Math.round(Math.pow(num, 1.0 / 3.0));                if (Math.pow(cubrt, 3) == (num)) {                    checked[cubrt] = true;                    ++cube_perms;                }            }            if (cube_perms == 5) {                return i;            }            System.out.println(i + , + cube_perms);        }    }    return 0;getPermutations()public static ArrayList<int[]> getPermutations(int[] arr) {    ArrayList<int[]> al = new ArrayList<int[]>();    Arrays.sort(arr);    do {        al.add(arr.clone());    } while (getNextPermDistinct(arr));    return al;}getNextPermDistinct()public static boolean getNextPermDistinct(int[] array) {    // Find longest non-increasing suffix    int i = array.length - 1;    while (i > 0 && array[i - 1] >= array[i])        i--;    // Now i is the head index of the suffix    // Are we at the last permutation already?    if (i <= 0)        return false;    // Let array[i - 1] be the pivot    // Find rightmost element that exceeds the pivot    int j = array.length - 1;    while (array[j] <= array[i - 1])        j--;    // Now the value array[j] will become the new pivot    // Assertion: j >= i    // Swap the pivot with j    int temp = array[i - 1];    array[i - 1] = array[j];    array[j] = temp;    // Reverse the suffix    j = array.length - 1;    while (i < j) {        temp = array[i];        array[i] = array[j];        array[j] = temp;        i++;        j--;    }    // Successfully computed the next permutation    return true;}longToArray()public static int[] longToArray(long i) {    int len = String.valueOf(i).length();    int[] arr = new int[len];    for (int j = 0; j < len; j++) {        arr[j] = (int)i % 10;        i /= 10;    }    return arr;}arrayToInt()public static int arrayToInt(int[] a) {    int num = 0;    for (int i = a.length - 1; i >= 0; i--) {        num += a[i] * Math.pow(10, a.length - i - 1);    }    return num;}
Finding the smallest cube for which exactly five permutations of its digits are cube
java;programming challenge;combinatorics
My main concern is that you will overflow Integers:You generate the cube using:long i_3 = i * i * i;Then after finding permutations you get test it with:int num = arrayToInt(x);int cubrt = (int) Math.round(Math.pow(num, 1.0 / 3.0));You appear to be iterating through cubes in ascending numeric order so any value of num should be greater than i_3. However, you are converting num to an int instead of a long (which is i_3's type).When you come to find the solution for 5 permutations you will hit the issue that the answer is 5027^3 but the int datatype can only store up to 1290^3 so you are going to overflow the integers.You've not shared the code for getPermutations, arrayToInt and longToArray so commenting on performance of your code is going to be difficult; however, since it seems to be the main focus of your request.Finding the cube root is much more intensive operation than cubing a number - you should try to do cube roots a little as possible.Similarly, finding permutations of a set can be intensive unless you implement an efficient algorithm (SteinhausJohnsonTrotter springs to mind; with a java implementation I did several years ago here).To improve iperformance I would suggest taking an entirely different approach. It is almost certainly more performant to iterate over all the values which when cubed give an n-digit result and compare those to see if they are permutations of each other (which can be done simply by converting the number to a string and sorting the digits into ascending order).My take on the code:import java.util.Arrays;import java.util.LinkedHashMap;import java.util.LinkedList;import java.util.Map;public class Cubics {    /**     * Finds the smallest n-digit cube for which exactly the required     * number of permutations of its digits are cube.     *      * @param numberOfDigits     *        The number of digits the cube is required to have.     * @param requiredNumberOfPermutations     *        The minimum permutations of the digits of a cube     *        that are required.     * @return A list of the permutations which are cubes in     *         ascending numeric order; or null if the requisite     *         number of permutations cannot be found.     */    public static final LinkedList<Long> findPermutationsOfCubeWithNumberOfDigits(            final int numberOfDigits,            final int requiredNumberOfPermutations    ){        // A hash map mapping the sorted digits of a number to a        // list of all cubes with those digits.        // A LinkedHashMap is used as the numbers will be added in ascending        // numeric order and this means the hash can be iterated over in        // entry order to find the minimum cubic value.        final LinkedHashMap<String,LinkedList<Long>> digitPermutations            = new LinkedHashMap<String,LinkedList<Long>>();        // Find the smallest integer which is the cube-root of an n-digit number        final long min = (long) Math.ceil( Math.pow( Math.pow( 10, numberOfDigits - 1), 1.0d / 3.0d ) );        // Find the largest integer which is the cube-root of an n-digit number        final long max = (long) Math.floor( Math.pow( Math.pow( 10,  numberOfDigits ) - 1, 1.0d / 3.0d ) );        // Test all the cubes between the min and max.        for ( long i = min; i < max; ++i )        {            final long cube = i * i * i;            // Sort the digits of the cube to get an unpermuted key.            final char[] chars = Long.toString( cube ).toCharArray();            Arrays.sort( chars );            final String key = new String( chars );            // Add the cube to the hash map.            if ( digitPermutations.containsKey( key ) )            {                digitPermutations.get( key ).addLast( cube );            }            else            {                final LinkedList<Long> values;                values = new LinkedList<Long>();                values.add( cube );                digitPermutations.put( key, values );            }        }        // Iterate over the cubed values in ascending numeric order        // checking whether there are at least the required number of        // permutations.        for ( final Map.Entry<String, LinkedList<Long>> entry : digitPermutations.entrySet() ){            final LinkedList<Long> cubes = entry.getValue();            if ( cubes.size() == requiredNumberOfPermutations ){                return cubes;            }        }        return null;    }    public static final void main( String[] args ){        int numberOfDigits = 0;        LinkedList<Long> cubes;        do {            ++numberOfDigits;            cubes = findPermutationsOfCubeWithNumberOfDigits( numberOfDigits, 5 );        } while ( cubes == null );        System.out.println( cubes );    }}