Array : Largest possible number

Question

Given an array of elements find the largest possible number that can be formed by using the elements of the array.
eg: 10 9
ans: 910
2 3 5 78
ans: 78532
100 9
ans: 9100

I know this problem has a solution using customized string comparator but i dont understand how it really works.

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>

    using namespace std;


    bool compare ( string a, string b )  
    {  
            return atoi( (a+b).c_str() ) < atoi((b+a).c_str() );  
    }

    int main()  
    {  
            vector<string> vs;  
            string s;  
            while ( cin >> s ) {  
                    vs.push_back(s);  
            }  
            sort( vs.begin(), vs.end(), compare );  
            for ( int i = vs.size()-1; i >= 0; i-- ) {  
                    cout << vs[i];  
            }  
    }   

Can anyone propose an algorithm to solve this problem? Explanation of the above comparator will be appreciated. Thank you

Answer 1

Indeed, if we have two strings S and T, we will most commonly concatenate them in lexicographically reverse order, to make the biggest digits come forward. However, this approach doesn't perfectly work, when one of these strings is a prefix for the other one.
Let T = SA, i.e. S is a prefix of T. We have two choices of concatenation: SSA and SAS. Obviously our choice will depend on which number is bigger: AS or SA. Below is the modification of your code which satisfies this algo:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;


bool compare ( string a, string b )  
{  
        int i, j;
        for( i = 0; i < a.size() && i < b.size(); ++i )
               if( a[ i ] != b[ i ] )
                     break;
        if( i < a.size() && i < b.size() ) //  if digit mismatch happened
               return a[ i ] < b[ i ];
        if( i == a.size() )                // a is a prefix for b
        {
               string suffix = b.substr( i );
               return a + suffix < suffix + a;
        }
        else                               // b is a prefix for a
        {
               string suffix = a.substr( i );
               return suffix + b < b + suffix;
        }
}

int main()  
{  
        vector<string> vs;  
        string s;  
        while ( cin >> s ) {  
                vs.push_back(s);  
        }  
        sort( vs.begin(), vs.end(), compare );  
        for ( int i = vs.size()-1; i >= 0; i-- ) {  
                cout << vs[i];  
        }  
}

Answer 2

The comparator compares two strings if the combination a+b comes before or after b+a. Thus e.g. it says that for input a=4; b=3 the string "34" is smaller than "43" and thus 4 should be before 3.

The numbers 2 3 5 78 will therefore be sorted into 78 5 3 2 and thus the result is 78532.

Answer 3

Just sort them into lexicographic order by comparing the digits from left to right. This way the larger digits appear first, thereby making the concatenated number larger.

EDIT: As Grigor points out, you must first reverse the strings, the sort them into reverse lex order, then concatenate and reverse the result.

Answer 4

You are using comparator operator to find the bigger of two possible numbers formed by concatenating two numbers(strings) in both possible ways a+b and b+a. Since you are interested in comparing magnitude of numbers, atoi() function is used to convert string to corresponding numbers.
But this conversion is not required. As the length of two strings a+b and b+a is same, lexicographical comparison is as good as magnitude of numbers. Conversion is only required when length of two stings compared is not equal.