Problem
Given a vector of non-negative integer numbers vec
, arrange the numbers in a way that they form the largest possible number and return its string representation.
Examples:
Input vec | Output |
[40, 45, 4, 5, 8] | "8545440" |
[0, 1, 2, 3] | "3210" |
[10, 5] | "510" |
[1] | "1" |
[0, 0] | "0" |
Solution
fn form_largest_number(vec: &mut Vec<u32>) -> String {
vec.sort_by(|a, b| {
(b.to_string() + a.to_string().as_str()).cmp(&(a.to_string() + b.to_string().as_str()))
});
if vec[0] == 0 {
String::from("0")
} else {
vec.iter()
.fold(String::from(""), |acc, x| acc + x.to_string().as_str())
}
}
Explanation
The first idea that could come to mind is just to convert the input vector of numbers vec
to the vector of strings and sort it alphabetically in descending order. It is almost what we need but not exactly - in some cases it would produce an incorrect result. For this example (vec = [40, 45, 4, 5, 8]
), this alphabetical sorting would put 40
in front of 4
, which would give us "404"
instead of the greater "440"
number.
Thus, to resolve the problem for numbers with the same leading digits, we could provide sort_by
with a comparator function that compares 2 strings in 2 different orders: b + a
and a + b
. In our example, a = 40, b = 4; b + a = "440"; a + b = "404"
. It means that "440".cmp("404")
call would return Ordering::Greater
, which means that b = 4
would be put before a = 40
in the ordering. And that is exactly what we need.
After the vector is ordered, we just need to concatenate numbers converted to strings. Also, we handle the special case when the vector contains only zeros - in that case, we return "0"
as the result.
Complexity
The time complexity of the solution is O(n*log n)
worst case (where n
is the size of the input vector), because that is the time complexity of the sort_by
implementation in rust.
The auxiliary space complexity is O(1)
(actually, it depends on the sort_by
implementation, which might allocate some extra space, but we assume that for small vectors a non-allocating sorting algorithm is used).