Largest Number formed from an Array

Given a list of non-negative integers, arrange them such that they form the largest possible number. The result should be a string, not an integer, as the number could be very large.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [3, 30, 34, 5, 9]
Output: "9534330"
Explanation: By arranging the numbers, the largest formed number is "9534330".

Example 2:
Input:
arr = [10, 2]
Output: "210"
Explanation: By arranging the numbers, the largest formed number is "210".

Example 3:
Input:
arr = [1, 20, 23, 4, 8]
Output: "8423201"
Explanation: By arranging the numbers, the largest formed number is "8423201".

Approach to make the Largest number formed from an array

  1. Convert Numbers to Strings:
    • Since we need to concatenate numbers and compare them, convert all integers in the array to strings. This will allow us to concatenate and compare the combined results easily.
  2. Custom Sorting:
    • Sort the array of strings using a custom comparator where two strings X and Y are compared based on which of X + Y or Y + X forms a larger number. If X + Y is larger, X should come before Y; otherwise, Y should come before X.
  3. Concatenate Sorted Strings:
    • After sorting, concatenate all strings in the sorted order to form the largest number.
  4. Handle Edge Case of Leading Zeros:
    • If the largest number is "0", return "0" instead of "000". This occurs when all elements are 0.

C++ Program to make the largest number from an array

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// Custom comparator function
bool compare(string X, string Y) {
    return X + Y > Y + X;
}

// Function to form the largest number from the array
string largestNumber(vector<int>& arr) {
    // Convert all integers to strings
    vector<string> strArr;
    for (int num : arr) {
        strArr.push_back(to_string(num));
    }

    // Sort strings using custom comparator
    sort(strArr.begin(), strArr.end(), compare);

    // Concatenate all strings in sorted order
    string result;
    for (string s : strArr) {
        result += s;
    }

    // Handle the case of leading zeros
    if (result[0] == '0') return "0";
    return result;
}

int main() {
    vector<int> arr = {3, 30, 34, 5, 9};
    cout << "Largest number formed: " << largestNumber(arr) << endl;
    return 0;
}

Java Program to make the largest number from an array

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

public class LargestNumber {

    // Custom comparator function
    private static class CustomComparator implements Comparator<String> {
        @Override
        public int compare(String X, String Y) {
            return (Y + X).compareTo(X + Y);
        }
    }

    // Function to form the largest number from the array
    public static String largestNumber(int[] arr) {
        // Convert all integers to strings
        String[] strArr = new String[arr.length];
        for (int i = 0; i < arr.length; i++) {
            strArr[i] = String.valueOf(arr[i]);
        }

        // Sort strings using custom comparator
        Arrays.sort(strArr, new CustomComparator());

        // Concatenate all strings in sorted order
        StringBuilder result = new StringBuilder();
        for (String s : strArr) {
            result.append(s);
        }

        // Handle the case of leading zeros
        if (result.charAt(0) == '0') return "0";
        return result.toString();
    }

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

Python Program to make the largest number from an array

python
from functools import cmp_to_key

# Custom comparator function
def compare(X, Y):
    return (Y + X) > (X + Y)

# Function to form the largest number from the array
def largest_number(arr):
    # Convert all integers to strings
    str_arr = list(map(str, arr))

    # Sort strings using custom comparator
    str_arr.sort(key=cmp_to_key(lambda X, Y: 1 if Y + X > X + Y else -1))

    # Concatenate all strings in sorted order
    result = ''.join(str_arr)

    # Handle the case of leading zeros
    return result if result[0] != '0' else '0'

# Example usage
if __name__ == "__main__":
    arr = [3, 30, 34, 5, 9]
    print("Largest number formed:", largest_number(arr))

Time Complexity: O(logn)

  • Sorting the array based on the custom comparator takes O(n log n), where n is the number of elements in the array.

Space Complexity: O(n)

  • The space complexity is O(n) due to the storage required for the string representations of the numbers and the temporary list used for sorting.

DSA

4284

828

Related Articles