Rearranging numbers to get the largest number

Question

Given a Integer, find the maximum number that can be formed from the digits.

• Input: 8754365
• Output: 8765543

private static int largestNumber(int data) {
 int num = data;
 int[] times = new int[10];
 while (num != 0) {
 if (num == 0) {
 break;
 }
 int val = num % 10;
 times[val]++;
 num /= 10;
 }
 String largestNumber = "";
 for (int i = 9; i >= 0; i--) {
 for (int j = 0; j < times[i]; j++) {
 largestNumber += i;
 }
 }
 return Integer.parseInt(largestNumber);
}

Is there any optimization or anything I can improve here?

• Simon Forsberg: I merged your most recent question into this one (moving the answer by Jerry Coffin here), as it seems that otherwise you wanted deletion of your new question. If you want to post a follow-up, you can do so but read How to post a follow-up question first.

Answer 1

while (num != 0) {
 if (num == 0) {
 break;
 }

That if is redundant and can be removed.

Using a StringBuilder for largestNumber is roughly twice as fast on my machine.

Avoiding strings altogether is faster still:

int largestNumber = 0;
for (int i = 9; i >= 0; i--) {
 for (int j = 0; j < times[i]; j++) {
 largestNumber = largestNumber * 10 + i;
 }
}
return largestNumber;

You might want to return a long instead of an int so that, for example, largestNumber(Integer.MAX_VALUE) returns 8776444321, as expected.

Answer 2

Naming is hard!

There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors.[1]

Have you tried reading your code out loud? The naming isn't very readable.

Looking at the specification I would expect the code to read something like:

Construct largest number from digits
 count digits
 create largest number from digit counts
 return result

Translating that to Java we get:

public static long constructLargestNumberFrom(int digits) {
 int[] digitCounts = getDigitCounts(digits);
 long largestNumber = constructLargestNumberFromDigitCounts(digitCounts);
 return largestNumber;
}

Where the two functions are the first and second half of your original code.

---

What about negative numbers?

You either need to disallow them:

if(digits < 0) {
 throw new IllegalArgumentException("digits must be greater than or equal to zero.");
}

Or handle them:

private static int[] getDigitCounts(int digits) {
 int[] digitCounts = new int[10];
 while (digits != 0) {
 int digit = Math.abs(digits % 10);
 digitCounts[digit]++;
 digits /= 10;
 }
 return digitCounts;
}

Notice the Math.abs call in the digit extraction. Just constructing the largest number from a negative number and ignoring the sign doesn't seem right though. It should be the least negative, i.e. the smallest number possible from the digits. With everything combined we get:

public static long constructLargestNumberFrom(int digits) {
 return constructLargestNumberFrom(digits, 10);
}
public static long constructLargestNumberFrom(int digits, int base) {
 if(base < 1) {
 throw new IllegalArgumentException("Base must be positive");
 }
 int[] digitCounts = getDigitCounts(digits, base);
 long largestNumber = digits < 0 ?
 constructSmallestNumberFromDigitCounts(digitCounts) * -1:
 constructLargestNumberFromDigitCounts(digitCounts);
 return largestNumber;
}
private static int[] getDigitCounts(int digits, int base) {
 assert base > 0 : "base must be greater than zero";
 int[] digitCounts = new int[base];
 while (digits != 0) {
 int digit = Math.abs(digits % base);
 digitCounts[digit]++;
 digits /= base;
 }
 return digitCounts;
}
private static long constructLargestNumberFromDigitCounts(int[] digitCounts) {
 assert digitCounts.length > 0 : "digitCounts must contains atleast one digit count.";
 assert Arrays.stream(digitCounts).allMatch(count -> count >= 0) : "Counts cannot be negative";
 int base = digitCounts.length;
 long largestNumber = 0;
 for (int digit = base - 1; digit >= 0; digit--) {
 for (int count = 0; count < digitCounts[digit]; count++) {
 largestNumber = largestNumber * base + digit;
 }
 }
 return largestNumber;
}
private static long constructSmallestNumberFromDigitCounts(int[] digitCounts) {
 assert digitCounts.length > 0 : "digitCounts must contains atleast one digit count.";
 assert Arrays.stream(digitCounts).allMatch(count -> count >= 0) : "Counts cannot be negative";
 int base = digitCounts.length;
 long smallestNumber = 0;
 for (int digit = 0; digit < base; digit++) {
 for (int count = 0; count < digitCounts[digit]; count++) {
 smallestNumber = smallestNumber * base + digit;
 }
 }
 return smallestNumber;
}

I also removed all the 10's scattered around the code and replaced them with base. I find this much more readable and now you can also do the same for other bases.

If you have any preconditions in you methods you should always clearly show them in your code.

• In public methods you should throw exceptions.
• In private methods you should do assertions.

Then anyone using your public methods will get a nice error and when you debug you can turn on assertions (with the vmflag -ea) and get nice errors when you don't follow your own guidelines. When assertions aren't turned on they're identical to empty statements and have close to zero performance implications.

Answer 3

Given a Integer, find the maximum number that can be formed from the digits

This is nothing more, than: returning a list of the digits in descending order.

A Java8 Solution would be:

private static int largestNumber(int i) {
 return Integer.parseInt(
 Arrays.stream((i + "")
 .split(""))
 .sorted((x,y)->y.compareTo(x))
 .collect(Collectors.joining())
 );
}

Or a conventional solution:

private static int largestNumber(int number) {
 String strings[]=(number+"").split("");
 Arrays.sort(strings, new Comparator<String>() {
 @Override
 public int compare(String t1, String t2) {
 return t2.compareTo(t1);
 }
 });
 StringBuilder sb=new StringBuilder(strings.length);
 for(String t:strings) sb.append(t);
 return Integer.parseInt(sb.toString());
}

• Grajdeanu Alex: How is this a code review?

Answer 4

Something like

char[] digits = String.valueOf(data).toCharArray()
Arrays.sort(digits)
// needs to be in descending order
for(int i = 0; i < digits.length / 2; i++) {
 char t = digits[i];
 digits[i] = digits[digits.length -i - 1];
 digits[digits.length -i - 1] = t;
}
Integer.parseInt(new String(digits))

is shorter and easier to understand

• mjolka: Except you would want to sort in descending order.
• kostya: @mjolka, you are right. It is surprisingly difficult to sort array in descending order in java. I think the fastest way would be to reverse it before converting to string. I will update the answer.

Answer 5

We are assuming positive integers hmms? I'm not doing a positive integer check below...

I didn't really want to bring up a Java 8 Stream solution, but the following is an alternative to @Thomas Junk's suggestion :

private static long getLargestNumber(int input) {
 return Long.parseLong(String.valueOf(input).chars().boxed()
 .sorted(Comparator.reverseOrder())
 .map(v -> Character.toString((char) v.intValue()))
 .collect(Collectors.joining()));
}

1. String.chars() gives us a Stream of char values.
2. boxed() the Stream so that we can apply sorted() using the reverseOrder() Comparator.
3. Map each Integer to the String representing the (implicit) char value, e.g. 49 to "1".
4. Join the Stream<String> together and pass it to Long.parseLong() (taking @mjolka's suggestion for a long return type).

The reason why I think a Stream-based solution is overblown for this, as much as I like to use it everywhere, is that a mathematics-based solution is going to be more efficient:

private static long getLargestNumber(int input) {
 int[] numbers = new int[10];
 for(int i = input; i != 0; i /= 10) {
 numbers[i % 10]++;
 }
 int counter = 0;
 long result = 0;
 for (int i = 0; i < 10; counter += numbers[i++]) {
 result += (int)((Math.pow(10, numbers[i]) * i - 1) / 9)
 * Math.pow(10, counter);
 }
 return result;
}

• Instead of a while-loop, I use a for-loop to keep the temporary iterator-variable i scoped within the loop.
• Inlined the expression i % 10 as the array index.
• counter keeps track of how many digits have been 'used'.
• counter += numbers[i++] is actually performing two increments for us:
  • increment counter by numbers[i],
  • then, increment i by 1 (using ++ in a postfix-increment form).
• To turn n times of v, e.g. four of 5-s into 5555, the mathematical expression is \$\frac{(10^n * m - 1)}{9}\$.
  • \$\frac n9\$ gives 0.nnn... but in order to work correctly for 9, we need to also multiply it by the number of digits required, then subtract 1. The subtraction still gives us enough precision for the int-casting later.
• 'Append' by multiplying the current number with \10ドル^{counter}\$.

Answer 6

I'm reasonably certain the largest number will be formed by sorting the digits in descending order.

Assuming that's correct, the best-case complexity is linear--you can generate the digits, then sort them with a bucket sort (aka. counting sort), and finally generate the result--all linear, so the overall result is linear. Assuming you use a counting sort, space complexity is basically constant--N integers, where N is the number base you're working in (10 for decimal).

• Simon Forsberg: Good idea with the bucket sort. That does indeed make it linear time with respect to the number of digits.

Answer 7

I believe that if we sort the numbers considering them as a string of digits, we can solve it easily and more efficiently. But, we have to take care of special cases where, if we are comparing numbers like 94 and 946, then after comparing 9 we have to go cyclic for 94, so we will compare 9 of 94 with 6 of 946. Then the numbers in decreasing order will be the answer that we look for.

 public static StringBuilder largestNumFormation (int[] arr){
 if (arr == null){
 throw new IllegalArgumentException();
 }
 String [] num = new String[arr.length];
 for (int i =0 ; i < arr.length ; i++){
 num[i] = String.valueOf(arr[i]); 
 }
 Arrays.sort(num, new Comparator<String>(){
 public int compare (String left, String right){
 String leftRight = left.concat(right);
 String rightLeft = right.concat(left);
 return rightLeft.compareTo(leftRight);
 } 
 });
 StringBuilder sb = new StringBuilder();
 for (String n : num){
 sb.append(n);
 }
 return sb;
}