# Maximum number

Problem:

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {154, 546, 548, 60}, the arrangement 6054854654 gives the largest value.

Input: First line contains an integer N , Next line contains N integers separated by space.

Output: Print the maximum number that can be obtained by using given numbers.

Constraints: 1<=N<=1000000

Solution:

First you need to have the numbers stored in an array of integers, then you do the following:

``````private static String largestNumber(int[] nums) {
String[] strings = new String[nums.length];

// convert the integer array into a string array
for (int i = 0; i < nums.length; i++) {
strings[i] = String.valueOf(nums[i]);
}

// sort the string array by comparing values a and b
// for example: "9" + "8" vs "8"+ "9", "98" > "89" so "98" goes first
Arrays.sort(strings, (a, b) -> (b + a).compareTo(a + b));

// combine the array into a big string
StringBuilder sb = new StringBuilder();
for (String s : strings) {
sb.append(s);
}

while (sb.charAt(0) == '0' && sb.length() > 1)
sb.deleteCharAt(0);

// return the final value as a string, since it can be large and cause overflow
return sb.toString();
}
``````

-- EDIT --

It seems that the java solution was a bit confusing with the lambda expression, so I will do the same logic, but in C++

``````int compareStrings(string a, string b)
{
// first append b to the end of a
string ab = a.append(b);

// then append a to the end of b
string ba = b.append(a);

// Now check which merge is bigger
if(ab.compare(ba) > 0){
return 1;
}
return 0;
}

void printLargest(vector<string> arr)
{
// sort from beginning to end using the compareString method.
// if any doubt, look at the online documentation for
// method specifications
sort(arr.begin(), arr.end(), compareStrings);

// now that the array is sorted, just print out
for (int i=0; i < arr.size() ; i++ )
cout << arr[i];
}
``````

Just call printLargest with a list of strings, such as

``````vector<string> arr;

//output should be 6054854654
arr.push_back("54");
arr.push_back("546");
arr.push_back("548");
arr.push_back("60");
printLargest(arr);
``````

Comment if you need anything else!