4
\$\begingroup\$

(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;
}
\$\endgroup\$
  • \$\begingroup\$ Just wanted to say that as the problem is stated '1' is a valid (a "bit" stretched) answer. \$\endgroup\$ – Vladimir Cravero Jun 4 '15 at 16:16
  • 1
    \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Jun 5 '15 at 13:32
  • \$\begingroup\$ @Vogel612 Ok I'll post a selfie answer \$\endgroup\$ – RE60K Jun 5 '15 at 15:05
6
\$\begingroup\$

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 (Steinhaus–Johnson–Trotter 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 );
    }
}
\$\endgroup\$
  • \$\begingroup\$ I'll Include that in question. [The three methods you're worried about.] \$\endgroup\$ – RE60K Jun 4 '15 at 13:26
  • \$\begingroup\$ I actually like your Idea. \$\endgroup\$ – RE60K Jun 5 '15 at 5:27
6
\$\begingroup\$

Change this code:

boolean[] checked = new boolean[999];
Arrays.fill(checked, false);
for (int i = 1; i < 999; i++) {
    if (!checked[i]) {

To this:

boolean[] checked = new boolean[999];
for (int i = 1; i < checked.length; i++) {
    if (!checked[i]) { 

The benefits:

  • boolean[] has all false values by default, no need to fill
  • Instead of iterating until some number, iterate until the something with a name that is required for the loop to work correctly, in this case checked.length

Other minor things:

  • The convention for naming variables is camelCase instead of snake_case
  • Refer to types by interfaces. Instead of ArrayList<int[]> perms =, use List<int[]> perms =
  • The getPermutations method returns List<int[]>, but you never actually use the int[] values, you immediately convert them to an int using arrayToInt. It seems it would be better if the method returned List<Integer> where the value are already converted into a form that you actually need.
\$\endgroup\$
  • \$\begingroup\$ question would be edited to incorporate more detail, thanks \$\endgroup\$ – RE60K Jun 4 '15 at 13:27
  • \$\begingroup\$ May I ask why you retain a boolean[] rather than suggesting a BitSet? \$\endgroup\$ – user22048 Jun 4 '15 at 15:47
  • \$\begingroup\$ To be honest I didn't look very close. Why, what benefit could a bitset bring here? \$\endgroup\$ – janos Jun 4 '15 at 15:56
5
\$\begingroup\$

This review will be mostly about style.

boolean[] checked = new boolean[999];
    Arrays.fill(checked, false);
    for (int i = 1; i < 999; i++) {

You're using 999 two times here, without stating why and without putting them in a constant.

long i_3 = i * i * i;

Wouldn't cube, i_cubed or something along those lines be more obvious? Have you considered using java.lang.Math.pow(i,3) instead?

int cubrt = (int) Math.round(Math.pow(num, 1.0 / 3.0));
if (Math.pow(cubrt, 3) == (num)) {

cube is already short, don't shorten it even further to cub. Especially since you use cube all around in your code, making this particular part inconsistent. The parentheses around num seem superfluous. Consider replacing these numbers with constants.

if (cube_perms == 5) {

Is 5 here a magic number (if so, put it in a constant) or the most obvious choice which shouldn't be changed? In case of the latter I'd still put it in a constant, to explicitly state it shouldn't be changed.

I'd also expect a comment here. If you insert a comment, don't make it something general like check if done but more along the lines of why this is the final situation.

\$\endgroup\$
2
\$\begingroup\$

I think most issues are already addressed by the other answers so I just like to share my solution to the problem in Java. What I do is just calculate the cube of every value and put the sorted result as key to two different maps. one that has the count for how many numbers have the same sorted cube and another for the lowest value that had it. When a certain number makes the count go to the wanted number of permutations it returns the lowest value from the other map. Theoretically it could have more permutations that's why it says at least X permutations but in practice it returns the right result and pretty fast too even for higher values of PERMUTATIONS

import java.util.Arrays;
import java.util.HashMap;

public class Main {
    public static final int PERMUTATIONS = 5;

    public static void main(String[] args) {
        HashMap<String, Integer> amounts = new HashMap<String, Integer>();
        HashMap<String, Long> lowest = new HashMap<String, Long>();
        long i = 1;
        while (true) {
            String sortedCube = sort(i * i * i);
            if (amounts.containsKey(sortedCube)) {
                int amount = amounts.get(sortedCube) + 1;
                amounts.put(sortedCube, amount);
                if (amount == PERMUTATIONS) {
                    long number = lowest.get(sortedCube);
                    System.out.println("The lowest number with at least " + PERMUTATIONS + " permutations is " + number + "^3 = " + number * number * number);
                    return;
                }
            } else {
                amounts.put(sortedCube, 1);
                lowest.put(sortedCube, i);
            }
            i++;
        }
    }

    public static String sort(long d) {
        char[] c = Long.toString(d).toCharArray();
        Arrays.sort(c);
        return new String(c);
    }
}
\$\endgroup\$
  • \$\begingroup\$ also nice to see is to remove final from PERMUTATIONS and instead of return; do a PERMUTATIONS++; to see higher permutations and you can see for example that the lowest number with at least 11 permutations actually has 15 permutations \$\endgroup\$ – Ivo Beckers Jun 4 '15 at 14:21
  • 2
    \$\begingroup\$ While it will get an answer - this does not always get the lowest answer. Imagine you have two keys to the HashMap which both require 1 more permutation to get the requisite amount; if the higher of the to keys gets its last permutation first then it will be returned even if the lower key has the required permutation at a higher value. \$\endgroup\$ – MT0 Jun 4 '15 at 19:41
  • \$\begingroup\$ @MT0 I guess you're right :) I didn't think of that. nice catch! \$\endgroup\$ – Ivo Beckers Jun 4 '15 at 19:43
  • \$\begingroup\$ @MT0 A solution might be that when the solution is found to continue checking numbers to see if another solution is found which has a lower lowest until the cube of the number has one digit more than the found solution. \$\endgroup\$ – Ivo Beckers Jun 4 '15 at 19:48
  • \$\begingroup\$ Yes - that's what I did in my solution. It checks all the cubes for an n-digit number and only then goes back and tests to find the lowest solution. (I just checked, the error does occur with 6 permutations - the minimum is 10002^3 but the solution above returns 11257^3) \$\endgroup\$ – MT0 Jun 4 '15 at 19:53
0
\$\begingroup\$

New Improved code (Time taken 0.217 seconds)

Map<Long, Long> sortedMap = new HashMap<Long, Long>();
    Map<Long, Integer> perms = new HashMap<Long, Integer>();
    long min = Long.MAX_VALUE;
    for (long i = 1; i < 9999; i++) {
        long i_3 = i * i * i;
        int[] x = longToArray(i_3);
        Arrays.sort(x);
        long sortedCube = arrayToLong(x);
        int len1 = String.valueOf(sortedCube).length();
        int len2 = String.valueOf(i_3).length();
        if (len1 != len2) {
            sortedCube *= Math.pow(10, (len2 - len1));
        }
        if (!perms.containsKey(sortedCube)) {
            perms.put(sortedCube, 1);
            sortedMap.put(sortedCube, i_3);
        } else {
            perms.put(sortedCube, perms.get(sortedCube) + 1);
            if (i_3 < sortedMap.get(sortedCube)) {
                sortedMap.put(sortedCube, i_3);
            }
        }
    }
    for (long x : perms.keySet()) {
        if (perms.get(x) == 5) {
            if (sortedMap.get(x) < min) {
                min = sortedMap.get(x);
            }
        }
    }
    return min;

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.