Largest Number

Given a list of non-negative integers, return the largest number that can be formed by their arrangement.

Eg. For the list [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Approach: We need sorting but in the modified way since if we have the number 9, 80 in the list then the largest number can be 980 but sorting will give 809. So, we modify sorting such that the for the pair(X, Y) in the list X comes first after sorting if XY > YX where XY represents concatenation of X and Y. Thus, for 9, 80, we will have the sorting result as 980 since 980 > 809.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

int myCompare(int a, int b){ string X = to_string(a); string Y = to_string(b); string XY = X.append(Y); string YX = Y.append(X); return XY.compare(YX) > 0 ? 1 : 0; } string Solution::largestNumber(const vector<int> &A) { vector<int> temp(A); string result = ""; int count = 0; for(int i = 0 ; i < A.size(); i++){ if(A[i] == 0){ count++; } } //handling all 0 vector if(count == A.size()){ result = "0"; return result; } //sort as per modified compare function sort(temp.begin(), temp.end(), myCompare); string out = ""; //make a string for the result for(int i = 0; i < A.size(); ++i){ result.append(to_string(temp[i])); } return result; }