algorithm - How can I manipulate an array to make the largest number? -

say have array of positive integers, manipulate them concatenation of integers of resultant array largest number possible. ex: {9,1,95,17,5}, result: 9955171

homework police: google phone interview question , no ndas signed ;).

as others have pointed out, lexicographic sort , concatenation close, not quite correct. example, numbers 5, 54, , 56 lexicographic sort produce {5, 54, 56} (in increasing order) or {56, 54, 5} (in decreasing order), want {56, 5, 54}, since produces largest number possible.

so want comparator 2 numbers somehow puts biggest digits first.

1. we can comparing individual digits of 2 numbers, have careful when step off end of 1 number if other number still has remaining digits. there lots of counters, arithmetic, , edge cases have right.

2. a cuter solution (also mentioned @sarp centel) achieves same result (1) lot less code. idea compare concatenation of 2 numbers reverse concatenation of numbers. of cruft have explicitly handle in (1) handled implicitly.

   for example, compare 56 , 5, we'd regular lexicographic comparison of 565 556. since 565 > 556, we'll 56 "bigger" 5, , should come first. similarly, comparing 54 , 5 means we'll test 545 < 554, tells 5 "bigger" 54.

here's simple example:

// c++0x: compile g++ -std=c++0x <filename> #include <iostream> #include <string> #include <algorithm> #include <vector>  int main() {   std::vector<std::string> v = {     "95", "96", "9", "54", "56", "5", "55", "556", "554", "1", "2", "3"   };   std::sort(v.begin(), v.end(),       [](const std::string &lhs, const std::string &rhs) {         // reverse order of comparison sort in descending order,         // otherwise we'll "big" numbers @ end of vector         return rhs+lhs < lhs+rhs;       });    (size_t = 0; < v.size(); ++i) {     std::cout << v[i] << ' ';   } } 

when run, code displays:

9 96 95 56 556 5 55 554 54 3 2 1