Arrange elements of given array to form largest number

By | April 24, 2016

Arrange elements of given array to form largest number

In this post we learn how to form the largest number from all the given elements of the input array.

Arrange elements of given array to form largest number Problem Statement:

Given an array of numbers,we need to arrange them in a way that yields the largest value possible of all the combinations that can be made.

Arrange elements of given array to form largest number Problem Example:

Let the input numbers given are : {1, 34, 3, 98, 9, 76, 45, 4}
Arrangement which gives the largest value : 998764543431

Arrange elements of given array to form largest number Problem Solution:

The first thing that we would like to try is to sort the numbers in decreasing array and print the result 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.
The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function MyCompare() and use it to sort numbers.

Algorithm:

  1. Given two numbers X and Y, MyCompare() must compare these two.
  2. We compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y).
  3. If XY is larger, then X should come before Y in output, else Y should come before.
  4. Eg -let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542
  5. Since 60542 is greater than 54260, we put Y first.

Arrange elements of given array to form largest number Problem Solution Code in C++:

  
#include <bits/stdc++.h> 
using namespace std;   

// A comparison function which is used by sort() in printLargest()
 int myCompare(string X, string Y) 
{     
    // first append Y at the end of X
    string XY = X.append(Y);
  
    // then append X at the end of Y
    string YX = Y.append(X);
 
    // Now see which of the two formed numbers is greater
    return XY.compare(YX) > 0 ? 1: 0;
}
/* The function that prints the arrangement with largest
   value. It accepts a vector of strings */
void printLargest(vector<string> arr)
{
    /*Sort the numbers using library sort funtion.It uses our
     comparison function myCompare() to compare two strings.*/
    sort(arr.begin(), arr.end(), myCompare);
 
    for (int i=0; i < arr.size() ; i++ )
        cout << arr[i];
}
 
// driver program to test above functions
int main()
{
    vector<string> arr;
 
    //output should be 998764543431
    arr.push_back("1");
    arr.push_back("34");
    arr.push_back("3");
    arr.push_back("98");
    arr.push_back("9");
    arr.push_back("76");
    arr.push_back("45");
    arr.push_back("4");
    printLargest(arr);
    
    return 0;
}

Output:

998764543431

Time Complexity:O(M logN)
Space Complexity: O(N)