Given a set of positive integers, the task is to write a function to order the integers in such a way that the concatenation of the numbers forms the largest possible integer and return this integer.
Use the following two sets of integers as tests and show your program output here.
- {1, 34, 3, 98, 9, 76, 45, 4}
- {54, 546, 548, 60}
- Possible algorithms
- A solution could be found by trying all combinations and return the best.
- Another way to solve this is to note that in the best arrangement, for any two adjacent original integers X and Y, the concatenation X followed by Y will be numerically greater than or equal to the concatenation Y followed by X.
- Yet another way to solve this is to pad ints to the same size by repeating the digits then sort using these repeated ints as a sort key.
#include <iostream> #include <sstream> #include <algorithm> #include <vector> #include <string> std::string findLargestConcat ( std::vector< int > & mynumbers ) { std::vector<std::string> concatnumbers ; std::sort ( mynumbers.begin( ) , mynumbers.end( ) ) ; do { std::ostringstream numberstream ; for ( int i : mynumbers ) numberstream << i ; concatnumbers.push_back( numberstream.str( ) ) ; } while ( std::next_permutation( mynumbers.begin( ) , mynumbers.end( ) )) ; return *( std::max_element( concatnumbers.begin( ) , concatnumbers.end( ) ) ) ; } int main( ) { std::vector<int> mynumbers = { 98, 76 , 45 , 34, 9 , 4 , 3 , 1 } ; std::vector<int> othernumbers = { 54 , 546 , 548 , 60 } ; std::cout << "The largest concatenated int is " << findLargestConcat( mynumbers ) << " !\n" ; std::cout << "And here it is " << findLargestConcat( othernumbers ) << " !\n" ; return 0 ; }
- Output:
The largest concatenated int is 998764543431 ! And here it is 6054854654 !
Content is available under GNU Free Documentation License 1.2.
