Largest Number | InterviewBit

Problem:

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.

Asked In:

1. AMAZON
2. GOLDMAN SACHS
3. MICROSOFT

Solution:

static bool compareString(string a,string b){

    return a+b > b+a;

}

string Solution::largestNumber(const vector<int> &A) {

    vector<string> str;

    for(int x:A)

        str.push_back(to_string(x));

    sort(str.begin(),str.end(),compareString);

    string res;

    bool flag = true;

    for(string x:str){

        if(x == "0")

            continue;

        flag = false;

        res += x;

    }        

    if(flag) res = "0";

    return res;

}