# 179. Largest Number (Medium)

https://leetcode.com/problems/largest-number/

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

Example 1:

```Input: `[10,2]`
Output: "`210"````

Example 2:

```Input: `[3,30,34,5,9]`
Output: "`9534330"`
```

Note: The result may be very large, so you need to return a string instead of an integer.

## Solutions

``````class Solution {

public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}

// 2276, 22
// 2272, 227
// 2273, 227

Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {

// max common divisor
private int getMCD(int m, int n) {
if (m < n) {
int temp = m;
m = n;
n = temp;
}

while (m % n != 0) {
int temp = m % n;
m = n;
n = temp;
}
return n;
}

// least common multiple
private int getLCM(int m, int n) {
return m * n / getMCD(m, n);
}

@Override
public int compare(Integer o1, Integer o2) {
String str1 = o1 + "";
String str2 = o2 + "";

int len = getLCM(str1.length(), str2.length());
// FIXME following condition statement is totally wrong
// for (int i = 1; i < len / str1.length(); i++) {
while (str1.length() < len) {
str1 += o1;
}

// for (int i = 1; i < len / str2.length(); i++) {
while (str2.length() < len) {
str2 += o2;
}

for (int i = 0; i < len; i++) {
if (str1.charAt(i) > str2.charAt(i)) {
return -1;
}

if (str1.charAt(i) < str2.charAt(i)) {
return 1;
}
}

// the order doesn't matter if str1 == str2
return 1;
}
});

for (int i = 0; i < nums.length; i++) {
}

String ans = "";
while (!queue.isEmpty()) {
ans += queue.poll();
}

// FIXME, following express will lead to overflow
// remove invalid zeros, say "00", "000"
// return Integer.valueOf(ans) + "";

while (!ans.isEmpty() && ans.length() > 1) {
if (ans.charAt(0) != '0') {
break;
}

ans = ans.substring(1);
}

return ans;
}
}
``````