What is the correct code to form largest number from a given int array?

Question

Problem statement is to form largest number from a given int array. For e.g. if the input array is {3, 30, 34, 5, 9} then the result should be 9534330. I tried following code but I am getting an exception in the if condition where I am trying to parse string into an int. Can you please tell how to resolve this?

import java.util.*;
import java.lang.Integer;
public class Console2 {
    public static void largestNumber(int[] array) {
     int s = array.length;
     String result = "0";
     for (int i = 0; i < s; i++) {
         int[] temp = new int[s];
         temp[i] = array[i];
         for (int j = 0; j < s; j++) {
             if ( i != j) {
                 temp[j] = array[j];
             }
         }
         if (Integer.parseInt(temp.toString()) > Integer.parseInt(result)) { // getting exception here !!!
             /*
             in the inner for loop, the temp array will store possible combinations of elements of
             the input array. so if i convert the temp array into string and then parse it to int, then
             i should be able to compare it with a result string (parsed to int) and store the highest
             possible number as string. once the outer for loop completes, the result will have highest 
             formed number which gets printed in this method.
              */
             result = temp.toString();
         }
     }
     System.out.println(result);
    }
    public static void main(String[] args) {
        int[] array = {3, 30, 34, 5, 9};
        largestNumber(array);
    }
}

Exception message:

Exception in thread "main" java.lang.NumberFormatException: For input string: "[I@7cc355be"
    at java.base/java.lang.NumberFormatException.forInputString(NumberFormatException.java:68)
    at java.base/java.lang.Integer.parseInt(Integer.java:652)
    at java.base/java.lang.Integer.parseInt(Integer.java:770)
    at Console2.largestNumber(Console2.java:15)
    at Console2.main(Console2.java:23)

Could you please go through your code and make `//comments` above the lines of code in the `if` as to *what you think the code is hoping to do* - I'd like to know what you think it should do so I can assess how your mental model/understanding differs from the reality — Caius Jard, Jul 11 '20 at 20:10
fun problem, I wonder if there is a clever way of doing this one — dang, Jul 11 '20 at 20:26
There is a clear way; convert the int array to strings and then sort them stringily rather than numerically, from largest to smallest, then join them into a string and parse the result to a long — Caius Jard, Jul 11 '20 at 20:30

Xaero Degreaz · Answer 1 · 2020-07-15T01:54:17.930

This should take your array of integers, and compare them to get the highest integer output available. It compares each element in the array against its concatenation with another, and the inverse.

This solution doesn't account for any negative numbers in the array.

You can see it in action here: https://ideone.com/LBAKE1

import java.util.Arrays;
import java.util.stream.Collectors;

class Main
{
    public static void main( String[] args )
    {
        runTests();
    }

    public static void runTests()
    {
        //# Input from original post
        assertEquals( largestNumber( new int[]{ 3, 30, 34, 5, 9 } ), "9534330" );
        //# Other tests from other comments
        assertEquals( largestNumber( new int[]{ 30, 301 } ), "30301" );
        assertEquals( largestNumber( new int[]{ 3, 30, 34, 90, 9 } ), "99034330" );
        //# Invalid assertion
        assertEquals( largestNumber( new int[]{ 1, 2, 3 } ), "123" );
    }

    public static String largestNumber( int[] array )
    {
        String result = Arrays
            .stream( array )
            .mapToObj( String::valueOf )
            .sorted( Main::sort )
            .collect( Collectors.joining() );
        System.out.println( result );
        return result;
    }

    public static int sort( String a, String b )
    {
        String t1 = a + b;
        String t2 = b + a;
        return Integer.compare( 0, Integer.valueOf( t1 ).compareTo( Integer.parseInt( t2 ) ) );
    }

    private static void assertEquals( String actual, String expected )
    {
        if ( !actual.equals( expected ) )
        {
            System.out.println( "ERROR: Expected " + expected + " but found " + actual );
        }
    }

}

Output:

9534330
30301
99034330
321
ERROR: Expected 123 but found 321

This solution prints `9533034`, but it should print `9533430` — Progman, Jul 11 '20 at 22:19
This doesn't work with `{30, 301}` as it will print `30130`, but it should print `30301`. — Progman, Jul 12 '20 at 07:36
@Progman - Thanks again. It was a brain tickler for sure. I took some time to do some proper testing, and also wrote a simple test suite compiled from your input values, and another value I saw from another post. If this clears things up, would you reconsider your downvote, please? — Xaero Degreaz, Jul 12 '20 at 09:45

score 1 · Answer 2 · answered Jul 11 '20 at 20:31

It seems your logic to combine the array into a single int for comparison is flawed.

Sorting them in an array is fine, but combining the elements of the array to a single number is incorrect, for instance in your code:

temp.toString()

returns an address ("[I@7cc355be") and not the combinations of the numbers as a String.

May I suggest you make temp a String and simply add the elements of the array to the end of the String:

 String temp = ""+array[i];;
 for (int j = 0; j < s; j++) {
     if ( i != j) {
         temp += ""+array[j];
     }
 }

Now when you call Integer.parseInt(temp) you should get a value you can compare to your currently stored result.

I think @Chirag_Debug wants to call the Array.toString(int[] a) method, which will convert the **contents** of the array to a string, not the array object itself represented as a string — dang, Jul 11 '20 at 20:36

Caius Jard · Answer 3 · 2020-07-12T05:54:29.300

With thanks to Progman for debugging and streaming advice

Here's a logic of it that works in .NET (I think in .net):

We sort the array by the result of padding the string version of the number out to X wide, using the first digit of the number as a pad char, so 3 -> 333, 30 -> 303, 39 -> 393. This means that 3 is greater than 30 - 32 but less than 35 - 39, and 30 is classed as greater than 301 (giving 30301 rather than 30130)

        int[] intA = new int[] {3, 30, 34, 5, 9};
        
        var res = string.Join("",                            //join using empty str as a separator
          intA                                               //the array
            .Select(i => i.ToString() )                       //projected to a collection of strings
            .OrderByDescending(s => s.PadRight(5, s.First())) //ordered descending by the result of padding the string out to 5 long using the first digit as a pad char
        );

I've managed to get this to a similarly compact form using java streaming

int[] intArray = { 1, 5, 4, 32 };


String res = Arrays
  .stream(intArray)
  .mapToObj(i -> new Object(){
     String n = Integer.toString(i); 
     String p = String.format("%-5s", i).replace(' ', (""+i).charAt(0));
  }) 
  .sorted((a,z) -> z.p.compareTo(a.p))
  .map(o -> o.n)
  .collect(Collectors.joining());

It projects the list of integers to a list of new objects that has a tostring'd int field plus a padded representation of the number as another string field. This list of objects is then sorted by the padded field and map used to pull the original string. The result is joined to a single string

It ceases to work if you have ints of more than 5 digits.. Realistically an int can't have more than 13 digits so you could just jump to using that. Or you could find the max int first, and Log10 it to get the number of digits you need to pad to. I'd expect it to be a micro optimisation at best unless you're using arrays with thousands of ints

This doesn't work correctly for numbers which have the same "prefix", but have a different length. As an example the array `{3, 30}` will be printed as "303", but should be "330". — Progman, Jul 11 '20 at 20:46
Now `{3, 39}` isn't working as it will result in `339` but it should be `393`. — Progman, Jul 11 '20 at 21:20
Heh.. OK.. my last attempt, I've got a lot on.. If it still has a bug with the "pad using last char of the string, I'll give up". Plus if you have any pointers on what to do for sorting the array in streaming API, it'd be helpful — Caius Jard, Jul 11 '20 at 21:41
It will fail with `{30, 301}`. It looks like it should be padded with the first digit, not with the last. — Progman, Jul 11 '20 at 22:08
You can use `sorted()` with a lambda comparator. It might look like this: `.sorted((a, b) -> String.format("%-5s", b).replace(' ', b.charAt(0)).compareTo(String.format("%-5s", a).replace(' ', a.charAt(0))))`. — Progman, Jul 11 '20 at 22:11

dang · Answer 4 · 2020-07-11T20:28:54.720

0

Your exception is likely due to the fact you are calling parseInt() on an int array not an int, so it is not actually defined. Could you print the full stack trace in an edit to the question?

edited Jul 11 '20 at 20:28

answered Jul 11 '20 at 20:26

dang

118
1
10

This isn't really what answers are for; this is more of a comment, and please don't ask for stacktraces to be dumped into comments - it would look horrendous – Caius Jard Jul 11 '20 at 20:28
@dang its not array which I am trying to parse but array.toString(). This is a legit String and should be able to parse. – Chirag_Debug Jul 11 '20 at 20:30
@Chirag_Debug check my comment under TM00's post – dang Jul 11 '20 at 20:37

Gerold Broser · Answer 5 · 2020-07-12T18:57:27.233

Try it online!

...
import static java.lang.System.out;
import static java.util.Arrays.stream;
...


public static int largestNumber( final int[] array ) {

    final int maxArrayElementLength = (int) Math.log10(
        stream( array )
            .peek( n -> {
                if ( n < 0 )
                    throw new IllegalArgumentException( "Array element < 0 not supported." );
            } )
            .max().getAsInt() )
        + 1;
    final StringBuilder sb = new StringBuilder();
    stream( array )
        .mapToObj( HelperInt::new )
        .peek( n -> n.valueToMaxLength( maxArrayElementLength ) )
        // descending order
        .sorted( ( n, m ) -> {
            if ( n.value > m.value )
                return -1;
            // equal widened numbers with shorter original length first
            if ( n.value == m.value )
                return n.length < m.length ? -1 : n.length == m.length ? 0 : 1;
            return 1;
        } )
        .peek( HelperInt::valueToOriginalLength )
        .forEach( n -> sb.append( n ) );

    return Integer.valueOf( sb.toString() );
} // largestNumber()

private static class HelperInt {

    int length;
    int value;
    int e;

    HelperInt( final int value ) {
        this.value = value;
        length = (int) Math.log10( value ) + 1;
    }

    void valueToMaxLength( final int maxLength ) {
        e = (int) Math.pow( 10, maxLength - length );
        value *= e;
    }

    void valueToOriginalLength() {
        if ( value > 0 )
            value /= e;
    }

    @Override
    public String toString() {
        return String.valueOf( value );
    }

} // HelperInt

Logic is getting failed for the input { 3, 30, 34, 90, 9 }, Output - 90934330, Expected - 99034330 — Shashank Mishra, Jul 12 '20 at 06:28

What is the correct code to form largest number from a given int array?

5 Answers5