Array: the maximum possible number

Question

Given that the array of elements finds the maximum possible number that can be formed using the elements of the array.
e.g. 10 9
ans: 910
2 3 5 78
En: 78532
100 9
ans: 9100

I know this problem has a solution using a custom string comparator, but I don't understand how this 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 suggest an algorithm to solve this problem? An explanation of the above comparator will be appreciated. Thanks you

Answer 1

In fact, if we have two lines S and T , we will most often concatenate them in the lexicographically reverse order to make the largest digits. However, this approach does not work perfectly when one of these lines is a prefix for the other.
Let T = SA , i.e. S is the prefix of T We have two concatenation options: SSA and SAS . Obviously, our choice will depend on which number is greater: AS or SA . The following is a modification of your code that satisfies this algorithm:

 #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 lines if the combination a+b precedes or after b+a . So, for example, he says that for input a=4; b=3 a=4; b=3 string "34" less than "43" and therefore 4 must be up to 3 .

Therefore, the numbers 2 3 5 78 will be sorted into 78 5 3 2 , and therefore the result will be 78532 .

Answer 3

Just arrange them in lexicographical order, comparing the numbers from left to right. Thus, large numbers first appear, thereby increasing the number of concatenations.

EDIT: As Grigor points out, you must first flip the lines, sort them in reverse order, then concatenate and cancel the result.

Answer 4

You use the comparator operator to search for a larger number of two possible numbers formed by combining two numbers (strings) in two possible ways a+b and b+a . Since you are interested in comparing numbers, the atoi() function is used to convert the string to the corresponding numbers.
But this conversion is not required. . Since the length of the two lines a+b and b+a same, the lexicographic comparison is as great as the magnitude of the numbers. Conversion is only required if the length of the two comparisons is not equal.

Answer 5

Given an array of integers, you can just do a few binary searches for the largest number. Each time you do this, concatenate the number at the end of the line (result) and remember to add the previously added numbers.