Leetcode 1363. Largest Multiple of Three

Problem Explanation

This problem requires finding the largest multiple of three that can be formed by concatenating some of the given digits in any order. It is important to note that the order of the digits matters. To form the largest number (which should also be multiple of 3), the highest numbers should be placed in the most significant positions.

For example, if our digits array is [8,1,9], the possible combinations are 819, 891, 918, 981, 189 and 198. Only 981 and 189 are multiples of three and 981 is the largest. Therefore, the output will be "981".

The approach to solve the problem uses a greedy algorithm and counting sort. The main idea is to place the highest digits in the most significant positions, and to deal with making the number a multiple of three by reducing the sum of digits by 1 or 2 (depending on the current sum) until it is divisible by 3. This reduction is performed by removing certain digits from the final number.

Solution Walkthrough

Let's walk through an example:

Given: digits array = [8,1,9]

Step 1: First, we create an array count to count the occurrences of each digit. After this step, count will look like this: [0,1,0,0,0,0,0,0,1,1].

Step 2: We calculate the sum of all the digits in our original array, which is 8 + 1 + 9 = 18. This sum is already divisible by 3, so no further reduction is required.

Step 3: If the sum was not divisible by 3, we would iteratively remove a digit whose value mod 3 equals the sum mod 3 (or 2*sum mod 3 if no such digit exists). This ensures that the sum becomes divisible by 3 without reducing it too much. We prefer to remove a lower digit to maximize the final number.

Step 4: Finally, we compose the largest number by appending count[digit] occurrences of each digit from high to low.

Step 5: After the above steps, the result is '981', which is a multiple of three and the largest number that can be formed from the input digits.

Step 6: Lastly, we handle a special case where the only valid output is '0', which occurs when all input digits are 0.

Python Solution

1
2python
3from typing import List
4class Solution:
5    def largestMultipleOfThree(self, digits: List[int]) -> str:
6        count = [0]*10
7        mods = [[1, 4, 7, 2, 5, 8], [2, 5, 8, 1, 4, 7]]
8        for d in digits:
9            count[d] += 1
10        mod = sum(digits) % 3
11        while mod:
12            if any(count[i] for i in mods[mod-1]):
13                for i in mods[mod-1]:
14                    if count[i]:
15                        count[i] -= 1
16                        break
17            else:
18                mod = 1 if mod == 2 else 2
19            mod = (sum(i * count[i] for i in range(10))) % 3
20        res = ''.join(str(i) * count[i] for i in range(9, -1, -1))
21        if res and res[0] == '0':
22            return '0'
23        return res

Java Solution

1
2java
3public class Solution {
4    public String largestMultipleOfThree(int[] digits) {
5        int[] count = new int[10], mods = {0, 0};
6        for (int d : digits)
7            count[d]++;
8        mods[0] = count[1] + count[4] + count[7];
9        mods[1] = count[2] + count[5] + count[8];
10        int mod = (mods[0] + 2 * mods[1]) % 3;
11        if (mod != 0) {
12            mod = 3 - mod;
13            if (mods[mod-1] >= 1)
14                mods[mod-1]--;
15            else
16                mods[3-mod]++;
17        }
18        StringBuilder res = new StringBuilder();
19        for (int i = 9; i >= 0; i--)
20            res.append(String.valueOf(i).repeat(Math.max(0, count[i])));
21        if (res.length() > 0 && res.charAt(0) == '0')
22            return "0";
23        return res.toString();
24    }
25}

JavaScript Solution

1
2javascript
3var largestMultipleOfThree = function(digits) {
4    let count = new Array(10).fill(0);
5    let mods = [1, 4, 7, 2, 5, 8, 3, 6, 9];
6    for (let d of digits)
7        count[d]++;
8    let mod = digits.reduce((a,b) => a+b, 0) % 3;
9    let reduceCount = ([target, replaced]) => {
10        for (let d of mods.slice((target - 1) * 3, target * 3))
11            while (mod % 3 != 0 && count[d] > 0) {
12                count[d]--;
13                mod = (mod + replaced) % 3;
14            }
15    };
16    if (mod != 0) {
17        if (mod == 1) reduceCount([1, 2]);
18        if (mod == 2) reduceCount([2, 1]);
19    }
20    if (count[0] == digits.length)
21        return '0';
22    return count.map((a,i) => String(i).repeat(a)).reverse().join('');
23};

C++ Solution

1
2cpp
3class Solution {
4public:
5    string largestMultipleOfThree(vector<int>& digits) {
6        vector<int> count(10);
7        vector<int> mods1 = {1, 4, 7, 2, 5, 8};
8        vector<int> mods2 = {2, 5, 8, 1, 4, 7};
9        int sum = accumulate(begin(digits), end(digits), 0);
10        for (const int digit : digits)
11            ++count[digit];
12        while (sum % 3 != 0)
13            for (int i : sum % 3 == 1 ? mods1 : mods2)
14                if (count[i]) {
15                    --count[i];
16                    sum -= i;
17                    break;
18                }
19        string res;
20        for (int digit = 9; digit >= 0; --digit)
21            res += string(count[digit], '0' + digit);
22        return (res.size() && res[0] == '0') ? "0" : res;
23    }
24};

C# Solution

1
2csharp
3public class Solution {
4    public string LargestMultipleOfThree(int[] digits) {
5        int[] count = new int[10];
6        int[] mods = {1, 4, 7, 2, 5, 8};
7        foreach (int digit in digits)
8            count[digit]++;
9        int sum = digits.Sum();
10        while (sum % 3 != 0)
11            foreach (int mod in sum % 3 == 1 ? mods : mods.Select(x => 3 - x))
12                if (count[mod] > 0) {
13                    count[mod]--;
14                    sum -= mod;
15                    break;
16                }        
17        string result = "";
18        for (int i = 9; i >= 0; --i)
19            result += new string((char)(i + '0'), count[i]);
20        return result[0] == '0' ? "0" : result;
21    }}

Rust Solution

1
2rust
3impl Solution {
4    pub fn largest_multiple_of_three(digits: Vec<i32>) -> String {
5        let mut counter = vec![0; 10];
6        let sum = digits.iter().fold(0, |sum, &x| {counter[x as usize] += 1; sum + x});
7        let remove_digits = |counter: &mut Vec<usize>, rm_list: Vec<usize>| {
8            for rm_target in rm_list {
9                while sum % 3 != 0 && counter[rm_target] > 0 {
10                    sum -= rm_target;
11                    counter[rm_target] -= 1;
12                }
13                if sum % 3 == 0{
14                    break;
15                }
16            }
17        };
18        match sum % 3 {
19            1 => remove_digits(&mut counter, vec![1, 4, 7, 2, 5, 8, 2, 5, 8]),
20            2 => remove_digits(&mut counter, vec![2, 5, 8, 1, 4, 7, 1, 4, 7]),
21            _ => (),
22        }
23        if counter[0] == digits.len(){
24            return String::from("0");
25        }
26        let mut res = String::new();
27        for i in (0..=9).rev(){
28            res.push_str(&i.to_string().repeat(counter[i]));
29        }
30        return res;
31    }
32}

In Rust, we follow a similar approach as the previous solutions. We aim to convert the sum of the digits vector to a multiple of 3 by removing minimal quantities from it. After each removal, we update sum. If after the removal sum % 3 == 0, we break the loop. If we obtained sum % 3 == 1 initially, we would remove individual numbers starting from the smallest ones whose residue module 3 is 1. If it's not possible, we remove pairs of numbers whose residue module 3 is 2. Similarly, if we obtained sum % 3 == 2 we would remove individual numbers whose residue module 3 is 2. If it's not possible, we remove pairs of numbers whose residue module 3 is 1. Then, we create our maximum number by looping in reverse order and appending to the answer the corresponding count of each number. Finally, if the input contains only 0s, we return '0'.