Follow

Follow

Rust Interview Puzzles: Form the largest number

go4fun.fun
·Feb 7, 2023·

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).

Rust Playground with this code