# [leetcode] Largest Number

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given `[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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

A wrong approach.  It’s plausible, but too messy. And it causes runtime error, I don’t figure out why so far.

```//Can input be empty?
//Can input contains illegal elements such as '002'?
struct {
bool operator()(int a, int b){
string sa = to_string(a);
string sb = to_string(b);
//This is to gurantee that sa is shorter than or equal to sb
//if(sa.size() > sb.size()){
//    string tmp = sa;
//    sa = sb;
//    sb = tmp;
//}
//BUG I can't swap sa and sb since it will mess up the result
size_t i = 0;
for(i = 0; i < sa.size() && i < sb.size(); i++){
if(sa[i] < sb[i]){
return false;
}
else if(sa[i] > sb[i]){
return true;
}
}
//sb is longer than sa
while(i < sb.size()){
if(sa[sa.size() - 1] < sb[i]){
return false;
}
else if(sa[sa.size() - 1] > sb[i]){
return true;
}
else{
i++;
}
}
//sa is longer than sb
while(i < sa.size()){
if(sb[sb.size() - 1] < sa[i]){
return true;
}
else if(sb[sb.size() - 1] > sa[i]){
return false;
}
else{
i++;
}
}
//sb is at the same length of sa or the longer part of sb contains the same digit to the last digit of sa
return true;//Or false, both are OK
}
} myLess;

class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), myLess);
string ans;
for(auto it = nums.begin(); it != nums.end(); it++){
ans = ans.append(to_string(*it));
}

if(ans[0] == '0') ans = "0";
return ans;
}
};```

Instead, write a compare function, if (to_string[a] + to_string[b] > to_string[b] + to_string[a]) we consider that a should be placed prior to b.

```class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b){
string sa = to_string(a);
string sb = to_string(b);
string ans1 = sa.append(sb);
string ans2 = sb.append(sa);
for(size_t i = 0; i < ans1.size(); i++){
if(ans1[i] < ans2[i]){
return false;
}
else if(ans1[i] > ans2[i]){
return true;
}
}
return false;
});
string ans;
for(size_t i = 0; i < nums.size(); i++){
ans = ans.append(to_string(nums[i]));
}
if(ans[0] == '0') ans = "0";
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.