Find Largest Number. Description - Given a list of non negative integers, arrange them such that they form the largest number

Question

For ex. Given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

public class Solution {

    public String largestNumber(final List<Integer> A) {

        String s = Integer.toString(A.get(0));
        for(int i = 1; i < A.size(); i++){
            s = myCompare(s, Integer.toString(A.get(i)));
        }

        return s;
    }

    public String myCompare(String X, String Y){
        if((Integer.valueOf(X+Y) > Integer.valueOf(Y+X))){
            return X+Y;
        }else{
            return Y+X;
        }
    }
}

What's wrong with my code. As it passes all test cases but when i am going to submit it, it shows-

Your submission stopped because of a runtime error, ex: division by zero, array index out of bounds, uncaught exception. You can try testing your code with custom input and try putting debug statements in your code. Exception in thread "main" java.lang.NumberFormatException: For input string: "9999999999" at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65) at java.lang.Integer.parseInt(Integer.java:583) at java.lang.Integer.valueOf(Integer.java:766) at Solution.myCompare(Solution.java:37) at Solution.largestNumber(Solution.java:30) at Main.main(Main.java:329) Your submission failed for the following input A : [ 9, 99, 999, 9999, 9998 ]

this type of error; How can i correct it. or what's the problem, as i am not able to figure out it.Can somebody help please.

Answer 1

Custom comparison of strings should be implemented to resolve this task:

1. If both strings have the same length, compare them as usual
2. Otherwise, find a shorter string, and compare the contents of the strings within the least length until a difference is detected.
3. If no difference is found, remove the "prefix" from the longer string and call compare method recursively.

Example implementation:

private static int compare(String a, String b) {
    if (a.length() == b.length()) return b.compareTo(a); // reverse order!
    
    boolean bShorter = a.length() > b.length();
    int i = 0, n = Math.min(a.length(), b.length());
    for (; i < n; i++) {
        int diff = b.charAt(i) - a.charAt(i); // reverse order
        if (diff != 0) return diff;
    }
    if (bShorter) {
        return compare(a.substring(n), b);
    }
    return compare(a, b.substring(n));
}

public static String largestNumber(List<Integer> a) {
    return a.stream()
            .map(String::valueOf)
            .sorted(MyClass::compare)
            .collect(Collectors.joining());
}

Tests:

System.out.println(largestNumber(Arrays.asList(3, 30, 34, 5, 9)));
System.out.println(largestNumber(Arrays.asList(4, 251, 2, 20, 25, 253, 28)));

Output

9534330         // 9 5 34 3 30
42825325251220  // 4 28 253 25 251 2 20

Answer 2

try to double test it when you get to those kind of task try to get to know the pattern of how things work then start coding

public String largestNumber(final List<Integer> A) {

    return A.stream()
            .map(Object::toString)
            .sorted((a, b) -> {
                        if (a.length() == b.length()) {
                            return b.compareTo(a);
                        } else if (a.length() < b.length()) {
                            for (int i = 0; i < a.length(); i++) {
                                if (a.charAt(i) != b.charAt(i)) {
                                    return Character.compare(b.charAt(i), a.charAt(i));
                                }
                            }
                            int i = a.length();
                            int temp = Character.compare(b.charAt(i), a.charAt(0));
                            while (temp == 0 && i < b.length() - 1) {
                                temp = Character.compare(b.charAt(++i), a.charAt(0));
                            }
                            if (temp == 0) {
                                return 1;
                            }
                            return temp;
                        } else {
                            for (int i = 0; i < b.length(); i++) {
                                if (b.charAt(i) != a.charAt(i)) {
                                    return Character.compare(a.charAt(i), b.charAt(i));
                                }
                            }
                            int i = b.length();
                            int temp = Character.compare(a.charAt(i), b.charAt(0));
                            while (temp == 0 && i < a.length() - 1) {
                                temp = Character.compare(a.charAt(++i), b.charAt(0));
                            }
                            if (temp == 0) {
                                return -1;
                            }
                            return -1 * temp;

                        }
                    }
            ).collect(Collectors.joining());

}

it cover those cases

1. if there 2 number with equal length which is the easiest part. it just compare thier value.

2. it get the number with shortest length then find the first smaller number at each position tens/handred and so on then the one with the smallest value is the smaller number.

3. if the shortest match all the number for the largest one then it check the last number of anyone of them (cause they already equaled in this case)and compare it with each number after it from the longest one the smallest number till it get smaller or larger number which make the whole number smaller or larger.

4. if step 3 find that all remaning number are equal to the last number then the longest is the bigger number

hope that help and hope it cover all cases and have a nice day :)

Answer 3

Some of the test input is large, which turns X+Y into a number that no longer fits in an int, thus, causing Integer.valueOf() to fail. You can get this error to occur locally rather easily: Integer.valueOf("9999999999") will do it. The inputs aren't even particularly large; the error prints which inputs fail.

Your myCompare method needs to be rewritten. You can't compare 2 strings by converting them to integer and then checking; the inputs form numbers that are too large.

A somewhat bizarre (and certainly not intended by this question) workaround is to use BigInteger instead. A more likely solution is to write a numeric comparison algorithm based on strings. I'm pretty sure just (X+Y).compareTo(Y+X) would do it - compare on 'natural order', i.e. how it would be printed in an address book. The problem with that kind of search is that e.g. "100" is considered 'smaller' than "99" because "100" starts with "1" which comes before "9". Same reason mr Anderson shows up before mr Zebra.

If you zero-strip a string containing a number (remove all leading zeroes, and I don't think you need to worry about it here, as you are given a precondition that all numbers are positive, i.e. larger than zero), then this algorithm will get you the larger number without resorting to converting to integers:

• If one of the two strings is shorter, that is the smaller number.
• If they are of same length, just do a basic alphabetic comparison: a.compareTo(b) where a and b are strings returns a negative number if a is smaller, a positive number if a is larger, and 0 if a and b are equal.