Home » Data Structure » Array Data Structure

Arrange given numbers to form the biggest number

C++ implementation to arrange given numbers to form the biggest number.
Submitted by Vikneshwar GK, on March 14, 2022

Consider an integer array, of size n. The task at hand is to form the maximum integer using the array element by appending them to one another.

Example:

Input:
array[]= {32, 1, 54, 35, 64}

Output:
array[] = {64, 54, 35, 32, 1} 

Explanation:
From the given array, 645435321 is the maximum integer 
that can be formed by rearranging the array.

Input:
array[] = {23, 15, 65, 105, 93}

Output:
array[] = {93, 65, 23, 15, 105}

Solution:

In order to solve this problem, we need to use a comparator-based sorting algorithm. The algorithm must use a custom comparison function, rather than a default one, to perform the required task. It involves the following steps:

• If num1 and num2 are the two numbers, then compare the numbers by appending num1 to num2 and num2 to num1.
• Place num1 and num2 accordingly based on the above step.
• Sort the array based on this comparison.
• Print the array elements.

C++ Implementation:

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

// custom comparison function
int myCompare(string num1, string num2)
{
    // append num2 to num1
    string num12 = num1.append(num2);

    // append num1 to num2
    string num21 = num2.append(num1);

    //compare the numbers
    return num12.compare(num21) > 0 ? 1 : 0;
}

// function to arrange the array elements
// to form the largest integer
void rearrangeArray(string array[], int length)
{
    // sort function with custom compare function
    sort(array, array + length, myCompare);
}

// Function to print the array
void printArray(string array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] <<" ";
    }
}

// Main function
int main()
{
    string array[100];
    int N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 32
Enter element 2: 1
Enter element 3: 54
Enter element 4: 35
Enter element 5: 64
64 54 35 32 1

Time Complexity: O(nlog(n)), where n is the length of the array.