Thursday, June 27, 2019

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!

>>>Return to Java Programs Page


Related Topics

  1. Armstrong Number or Not Java Program
  2. Java Program to Reverse a Number
  3. Fibonacci Series Program in Java
  4. Print odd-even numbers using threads and wait-notify
  5. Converting double to int in Java

You may also like-

  1. Invoking getters and setters using Reflection - Java Program
  2. How to create PDF from XML using Apache FOP
  3. Unzipping files in Java
  4. Reading all files in a folder - Java Program
  5. Ternary operator in Java
  6. Searching within a String using indexOf(), lastIndexOf() and contains() methods
  7. Volatile in Java
  8. What is Dependency Injection in Spring

No comments:

Post a Comment