Arrange given numbers to form the biggest number

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

Solution:

A simple solution that comes to our mind is to sort all numbers in descending order, but simply sorting doesn’t work. For example, 548 is greater than 60, but in output 60 comes before 548. As a second example, 98 is greater than 9, but 9 comes before 98 in output.

1st approach:

We would be using a comparator, we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before.

For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Vector;

public class OneWay {

//my main method starts here
    public static void main(String[] args) {
        Vector<String> arr = new Vector<>();
        // output should be 6054854654
        arr.add("1");
        arr.add("34");
        arr.add("3");
        arr.add("98");
        arr.add("9");
        arr.add("76");
        arr.add("45");
        arr.add("4");
//calling the function
        printLargest(arr);
    }

    private static void printLargest(Vector<String> arr) {
// using comparator for comparing the numbers after appending 
// to each other and then sorting 
        Collections.sort(arr,new Comparator<String>() {
            @Override public int compare(String X , String Y){
                // first append Y at the end of X
                String XY = X+Y;
                // then append X at the end of Y
                String YX = Y+X;
                // Now see which of the two formed numbers is greater
                return XY.compareTo(YX) > 0 ? -1 : 1;
            }
            
        });
// Iterator is used for traversing through the array to get the final output
        Iterator it = arr.iterator();
        while(it.hasNext()){
            System.out.print(it.next());
        }
    }
}

//Time Complexity:  O(n log n)
// Auxiliary Space: O(X), Where X is the maximum number of digits in the
// given numbers.

2nd Approach:

import java.util.Arrays;

public class SecondWay {
    public static void main(String[] args) {
        int arr[] = { 3, 30, 34, 5, 9 };
//calling the function
        printLargest(arr);
    }

    private static String printLargest(int[] arr) {
// if the arr is null or it's empty then return empty string
        if (arr == null || arr.length == 0)
            return "";

// creating a string array of size same as arr size
        String[] str = new String[arr.length];

        // convert all iteration to string and add them to string array

        for (int i = 0; i < arr.length; i++) {

// here we are storing all elements of array in str array in string format
            str[i] = String.valueOf(arr[i]);

        }
        Arrays.sort(str, (str1, str2) -> (str2 + str1).compareTo(str1 + str2));

        if (str[0].charAt(0) == '0')
            return "0";
// stringbuilder is like arraylist , as it is dynamic and we used it here 
// bcz string are immutable
        StringBuilder sb = new StringBuilder();

        for (String s : str) {

            sb.append(s);

        }

        String result = sb.toString();

        return result;

    }
}

Arrays.sort(str, (str1, str2) -> (str2 + str1).compareTo(str1 + str2));

This statement is sorting an array of strings, “str”, using the Arrays.sort() method, and a custom comparator.

The Arrays.sort() method is a built-in method in Java that sorts an array of elements in ascending order. In this case, it’s sorting an array of strings, “str”.

The custom comparator is defined as a lambda expression, (str1, str2) -> (str2 + str1).compareTo(str1 + str2). It takes two strings as input (str1 and str2) and compares them using the compareTo() method.

The compareTo() method is called on the concatenation of str2 and str1, and str1 and str2. It compares the lexicographic order of these two concatenated strings and returns a negative integer, zero, or a positive integer, depending on whether the first concatenated string is less than, equal to, or greater than the second concatenated string.

So the lambda expression compares the concatenation of str1 and str2 with the concatenation of str2 and str1. Based on the comparison it returns a negative, zero, or positive value which is used for sorting the array.

In summary, this statement is using the Arrays.sort() method to sort an array of strings, “str”, in ascending order, using a custom comparator that compares the lexicographic order of two concatenated strings (str1 + str2) and (str2 + str1) to determine the relative order of the two strings.