Largest Number Forming from Array of Integers in Java

Largest Number Forming from Array of Integers

Problem Statement

Given a list of non-negative integers, arrange them such that they form the largest possible number. The resulting number should be returned as a string.

Example:

Input: {3, 30, 34, 5, 9}
Output: "9534330"

The largest possible number formed is "9534330", and this should be returned as a string.

Step-by-Step Code Explanation

Let’s break down the code to make it easier for beginners to understand.

Step 1: Convert the Integer Array to String Array

We first need to convert the integer array into a string array. This is because when we concatenate numbers, it’s easier to work with them as strings.

String[] numStr = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
    numStr[i] = String.valueOf(numbers[i]); // Convert each number to a string
}

In the above loop, we iterate through each number in the original array, convert it to a string using String.valueOf() and store it in the numStr array.

Step 2: Sort the String Array Using a Custom Comparator

The key part of this solution is the sorting step. We need to sort the string array in such a way that when the numbers are concatenated, they form the largest number possible. For example, 9 should come before 34 because 934 is greater than 349.

We achieve this by using a custom comparator that compares two strings (numbers) based on their concatenated values:

Arrays.sort(numStr, new Comparator<String>() {
    @Override
    public int compare(String a, String b) {
        String order1 = a + b; // Concatenate a followed by b
        String order2 = b + a; // Concatenate b followed by a
        return order2.compareTo(order1); // Sort in descending order
    }
});

We concatenate both strings in two different orders: a + b and b + a.
If a + b is greater than b + a, then a should come before b in the sorted array.

Step 3: Handle Edge Case for Leading Zeros

An important edge case is when all the numbers are 0, such as {0, 0, 0}. In such cases, the result should be "0", not "000". To handle this:

if (numStr[0].equals("0")) {
    return "0"; // If the largest number is "0", return "0"
}

If the first number in the sorted array is "0", that means all numbers are zero, so we return "0".

Step 4: Concatenate the Strings to Form the Largest Number

Once the array is sorted, we simply concatenate all the elements in the array to form the largest number:

StringBuilder largestNumber = new StringBuilder();
for (String num : numStr) {
    largestNumber.append(num);
}

return largestNumber.toString();

We use a StringBuilder to efficiently append each number in the sorted array, and then convert it into a string to return the final result.

Complete Java Code

Here is the complete code to solve the problem:

import java.util.Arrays;
import java.util.Comparator;

public class LargestNumber {
    public static void main(String[] args) {
        int[] numbers = {3, 30, 34, 5, 9};
        System.out.println("Largest number: " + formLargestNumber(numbers));
    }

    public static String formLargestNumber(int[] numbers) {
        // Step 1: Convert the integer array to a string array
        String[] numStr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            numStr[i] = String.valueOf(numbers[i]); // Convert each number to a string
        }

        // Step 2: Sort the string array using a custom Comparator
        Arrays.sort(numStr, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String order1 = a + b; // Concatenate a followed by b
                String order2 = b + a; // Concatenate b followed by a
                return order2.compareTo(order1); // Sort in descending order
            }
        });

        // Step 3: Handle the edge case where the largest number is "0"
        if (numStr[0].equals("0")) {
            return "0"; // If the largest number is "0", return "0"
        }

        // Step 4: Build the largest number by concatenating the sorted strings
        StringBuilder largestNumber = new StringBuilder();
        for (String num : numStr) {
            largestNumber.append(num);
        }

        return largestNumber.toString();
    }
}

Output Example

For the input:

Numbers: {3, 30, 34, 5, 9}

The output will be:

Largest number: 9534330

Key Learning Points

String Manipulation: Convert integers to strings to handle concatenation.
Custom Sorting: Use a comparator to sort based on concatenation logic.
Edge Case Handling: Ensure that all zeros are handled correctly.
StringBuilder: Efficiently build the final result string by appending the sorted numbers.

This solution is a good example of using custom sorting and string manipulation to solve a non-trivial problem. Perfect for helping beginners understand sorting with complex comparison logic!