Sunday, July 3, 2022

Arrange Non-Negative Integers to Form Largest Number - Java Program

In this post, we’ll see Java code to solve the stated problem “Given a list of non-negative integers arrange them to form the largest number”.

As example– If list of numbers is [2, 35, 23, 6, 8] then the Java program should output the largest number as 8635232.

If list of non-negative integers is [7, 70] then the largest number should be 770.

Logic for the Solution

Logic for Java program to form the biggest number by arranging the given list of numbers is as follows-

If you compare these integers after converting them to strings and arrange them in decreasing order then you will get the biggest number.

So the question arises why as String? Reason is Strings are compared in lexicographic order which means if two strings “Always” and “Be” are compared then only by comparing first character it is determined that “Be” will be placed first (if order is decreasing order).

Same way for Strings “6” and “53”, string “6” will be placed first (if order is decreasing order) because comparing first character itself determines that order. In String comparison it won’t go by the value. So you can see how it helps as you get the largest number 653 by this comparison.

Another thing is you will have to write your own comparator to have a decreasing order since sorting is done in natural order by default.

Java program to arrange integers to form largest number

```import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class LargestNum {

public static void main(String[] args) {
List<Integer> numList = Arrays.asList(2, 35, 23, 6, 8);

formLargestNum(numList);
}

/**
* Method used to form the largest number using the
* numbers passed in the list
* @param numList
*/
private static void formLargestNum(List<Integer> numList){
Collections.sort(numList, new Comparator<Integer>() {

@Override
public int compare(Integer num1, Integer num2) {
String a = num1.toString() + num2.toString();
String b = num2.toString() + num1.toString();

System.out.println("a- " + a);
System.out.println("b- " + b);
return b.compareTo(a);
}
});
// Displaying number
for(Integer i : numList){
System.out.print(i);
}
}
}
```

Output

```8635232
```

One thing you would have noticed here is the way concatenation of the strings is done

```String a = num1.toString() + num2.toString();
String b = num2.toString() + num1.toString();
```

You may use the single string also like below-

```String a = num1.toString();
String b = num2.toString();
```

It may run fine in most of the cases but it will give problem with Strings like “7” and “70” where it will place 70 before 7. While comparing, since the first character is equal in this case, so comparison of second character will be done which will result in 70 coming before 7 and negate the effect of using String instead of number. By concatenating the two strings you can avoid this problem.

That's all for this topic Arrange Non-Negative Integers to Form Largest Number - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!