Largest Number - Interviewbit Solution
Problem: Largest Number
Problem Description:
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.
Solution:
string Solution::largestNumber(const vector<int> &A) { vector<string> arr; int i,j,k, size=A.size(); for(i=0;i<size;i++){ arr.push_back(to_string(A[i])); } for(i=0;i<size-1;i++){ for(j=i;j<size;j++){ int s1 = arr[i].size(); int s2 = arr[j].size(); int itr = s1>s2 ? s1 : s2; for(k=0 ; k<itr ; k++){ if(arr[i][k%s1] > arr[j][k%s2]){ break; } if(arr[i][k%s1] < arr[j][k%s2]){ swap(arr[i],arr[j]); break; } } } } string ans; for(i=0;i<size;i++){ ans=ans+arr[i]; } if(ans[0]=='0'){return "0";} return ans; }