# LeetCode - Largest Number

## Problem statement

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Problem statement taken from: https://leetcode.com/problems/largest-number

Example 1:

``````Input: nums = [10, 2]
Output: '210'
``````

Example 2:

``````Input: nums = [3, 30, 34, 5, 9]
Output: '9534330'
``````

Constraints:

``````- 1 <= nums.length <= 100
- 0 <= nums[i] <= 10^9
``````

### Explanation

#### Sorting using a custom comparator

To construct the largest number, we need to place the largest digits at the most significant bit.

We need to convert each integer to a string and then sort the array of strings. Note We cannot perform sorting on the number of integers. For e.g., if we have numbers [9, 30, 15] and sort them in descending order it will result in [30, 15, 9] and the number constructed is 30159. The largest number is 93015.

Let's check the algorithm:

``````// largestNumber function
- if nums.size() == 0
- return ''

- initialize vector<string> numbers
i = 0

- loop for i < nums.size(); i++
// convert integer to string and push in the array
- numbers.push_back(std::to_string(nums[i]))

- sort(numbers.begin(), numbers.end(), cmp)

- set ans = ''

- loop for i = 0; i < numbers.size(); i++
- ans = ans + numbers[i]

- return ans[0] == '0' ? '0' : ans

// cmp function
cmp(string a, string b)
- return a + b > b + a
``````

#### C++ solution

``````class Solution {
static bool cmp(string a, string b){
return a + b > b + a;
};

public:
string largestNumber(vector<int>& nums) {
if(nums.size() == 0){
return '';
}

vector<string> numbers;
int i = 0;

for(; i < nums.size(); i++){
numbers.push_back(std::to_string(nums[i]));
}

sort(numbers.begin(), numbers.end(), cmp);
string ans = '';

for(i = 0; i < numbers.size(); i++){
ans += numbers[i];
}

return ans[0] == '0' ? '0' : ans;
}
};``````

#### Golang solution

``````func largestNumber(nums []int) string {
if len(nums) == 0 {
return ''
}

numbers := make([]string, len(nums))
i := 0

for i < len(nums) {
numbers = append(numbers, strconv.Itoa(nums[i]))
i++
}

sort.Slice(numbers, func(a, b int) bool { return numbers[a] + numbers[b] > numbers[b] + numbers[a] })

ans := ''

for _, v := range numbers { ans += v }

if ans[0] == '0' {
return '0'
}

return ans
}``````

#### Javascript solution

``````var largestNumber = function(nums) {
if( nums.length == 0 ) {
return '';
}

let numbers = [];

for( let i = 0; i < nums.length; i++ ) {
numbers.push(nums[i].toString());
}

numbers.sort(function (x, y) {
return x + y > y + x ? -1 : 1;
});

let ans = '';

for( i = 0; i < numbers.length; i++ ){
ans += numbers[i];
}

return ans[0] == '0' ? '0' : ans;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: nums = [3, 30, 34, 5, 9]

Step 1: nums.size() == 0
5 == 0
false

Step 2: vector<string> numbers;
int i = 0;

Step 3: loop i < nums.size()
0 < 5
true

numbers.push_back(std::to_string(nums[i]))

so the loop iterates from 0 to 4, and we append the string numbers

numbers = ['3', '30', '34', '5', '9']

Step 4: sort(numbers.begin(), numbers.end(), cmp)

// in cmp function
Step 5: return a + b > b + a

so for first two element we check
'3' + '30' > '30' + '3'
'330' > '303'
true

'3' + '34' > '34' + '3'
'334' > '343'
false

'5' + '34' > '34' + '5'
'534' > '345'
true

'9' + '5' > '5' + '9'
'95' > '59'
true

The final array is ['9', '5', '34', '3', '30'].

Step 6: string ans = ''

Step 7: loop for(i = 0; i < numbers.size(); i++)
- ans += numbers[i]
ans is set to '9534330'

Step 8: ans[0] == '0'
'9' == '0'
false
return ans

So we return the result as '9534330'.
``````