Code Implementation

class Solution:
    def largestMultipleOfThree(self, digits):
        count = [0] * 10
        total = 0
        for d in digits:
            count[d] += 1
            total += d

        def remove(rem, times):
            for _ in range(times):
                for i in range(1, 10):
                    if i % 3 == rem and count[i] > 0:
                        count[i] -= 1
                        break
                else:
                    return False
            return True

        if total % 3 == 1:
            if not remove(1, 1):
                if not remove(2, 2):
                    return ""
        elif total % 3 == 2:
            if not remove(2, 1):
                if not remove(1, 2):
                    return ""

        res = []
        for i in range(9, -1, -1):
            res += [str(i)] * count[i]
        if not res:
            return ""
        if res[0] == "0":
            return "0"
        return "".join(res)
      

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> count(10, 0);
        int total = 0;
        for (int d : digits) {
            count[d]++;
            total += d;
        }
        auto remove = [&](int rem, int times) {
            for (int t = 0; t < times; ++t) {
                bool found = false;
                for (int i = 1; i <= 9; ++i) {
                    if (i % 3 == rem && count[i] > 0) {
                        count[i]--;
                        found = true;
                        break;
                    }
                }
                if (!found) return false;
            }
            return true;
        };
        if (total % 3 == 1) {
            if (!remove(1, 1)) {
                if (!remove(2, 2)) return "";
            }
        } else if (total % 3 == 2) {
            if (!remove(2, 1)) {
                if (!remove(1, 2)) return "";
            }
        }
        string res = "";
        for (int i = 9; i >= 0; --i) {
            res.append(count[i], '0' + i);
        }
        if (res.empty()) return "";
        if (res[0] == '0') return "0";
        return res;
    }
};
      

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        int[] count = new int[10];
        int total = 0;
        for (int d : digits) {
            count[d]++;
            total += d;
        }
        java.util.function.BiFunction<Integer, Integer, Boolean> remove = (rem, times) -> {
            for (int t = 0; t < times; ++t) {
                boolean found = false;
                for (int i = 1; i <= 9; ++i) {
                    if (i % 3 == rem && count[i] > 0) {
                        count[i]--;
                        found = true;
                        break;
                    }
                }
                if (!found) return false;
            }
            return true;
        };
        if (total % 3 == 1) {
            if (!remove.apply(1, 1)) {
                if (!remove.apply(2, 2)) return "";
            }
        } else if (total % 3 == 2) {
            if (!remove.apply(2, 1)) {
                if (!remove.apply(1, 2)) return "";
            }
        }
        StringBuilder res = new StringBuilder();
        for (int i = 9; i >= 0; --i) {
            for (int j = 0; j < count[i]; ++j) {
                res.append(i);
            }
        }
        if (res.length() == 0) return "";
        if (res.charAt(0) == '0') return "0";
        return res.toString();
    }
}
      

var largestMultipleOfThree = function(digits) {
    let count = Array(10).fill(0);
    let total = 0;
    for (let d of digits) {
        count[d]++;
        total += d;
    }
    function remove(rem, times) {
        for (let t = 0; t < times; ++t) {
            let found = false;
            for (let i = 1; i <= 9; ++i) {
                if (i % 3 === rem && count[i] > 0) {
                    count[i]--;
                    found = true;
                    break;
                }
            }
            if (!found) return false;
        }
        return true;
    }
    if (total % 3 === 1) {
        if (!remove(1, 1)) {
            if (!remove(2, 2)) return "";
        }
    } else if (total % 3 === 2) {
        if (!remove(2, 1)) {
            if (!remove(1, 2)) return "";
        }
    }
    let res = [];
    for (let i = 9; i >= 0; --i) {
        for (let j = 0; j < count[i]; ++j) {
            res.push('' + i);
        }
    }
    if (res.length === 0) return "";
    if (res[0] === "0") return "0";
    return res.join('');
};
      

Problem Description

Given a list of digits (with values from 0 to 9), you are asked to form the largest possible number (as a string) using any or all of the digits in the array such that the resulting number is a multiple of three. Each digit in the input array digits can be used at most once (no reuse), and you can arrange the digits in any order. If there is no valid number that is a multiple of three, return an empty string. If the answer is "0" (i.e., all digits are zero), return exactly "0".

• Each digit can be used at most once.
• Return the largest possible number (as a string) divisible by three.
• If no such number exists, return an empty string.
• If the answer is zero, return "0" (not "000...").

Thought Process

At first glance, one might think about generating all possible combinations of the digits, forming numbers, and checking if they are divisible by three. However, this brute-force approach quickly becomes infeasible as the number of digits increases, due to the exponential number of possible combinations and permutations.

We need a smarter way. Since divisibility by three depends only on the sum of the digits, we can use this property to our advantage. Our goal is to pick as many digits as possible (to maximize the number's length), and arrange them in descending order (to get the largest number), while ensuring the sum of the selected digits is a multiple of three.

If the sum isn't already a multiple of three, we can try removing the smallest number(s) of digits necessary to make it so. We should remove the minimal possible digits (and the smallest ones) to keep the final number as large as possible.

Solution Approach

• Step 1: Count Digits and Compute Total Sum
  Count how many times each digit appears in the input, and calculate the sum of all digits.
• Step 2: Check Sum Modulo 3
  If the sum is already divisible by three, we can use all digits.
• Step 3: Remove Minimal Digits to Fix Modulo
  If the sum modulo 3 is 1, we need to remove either one digit with remainder 1 (modulo 3), or two digits with remainder 2.
  If the sum modulo 3 is 2, we need to remove either one digit with remainder 2, or two digits with remainder 1.
  Always try to remove the smallest possible digits to maximize the final number.
• Step 4: Construct the Largest Number
  After removing the necessary digits, arrange the remaining digits in descending order to form the largest number.
• Step 5: Handle Edge Cases
  If the resulting number is empty, return an empty string.
  If the largest digit is zero (i.e., all digits are zero), return "0" (not multiple zeros).

This approach leverages the mathematical property of multiples of three and uses simple counting and sorting to ensure efficiency.

Example Walkthrough

Example Input: [8, 1, 9]

• Step 1: Count digits: 8 (1), 1 (1), 9 (1). Total sum = 8 + 1 + 9 = 18.
• Step 2: 18 % 3 = 0, so the sum is divisible by three.
• Step 3: No need to remove any digits.
• Step 4: Arrange digits in descending order: 9, 8, 1. Result: "981".
• Step 5: All digits used. Return "981".

Another Example: [8, 6, 7, 1, 0]

• Step 1: Count digits, sum = 8 + 6 + 7 + 1 + 0 = 22.
• Step 2: 22 % 3 = 1. Need to remove one digit with remainder 1 (modulo 3), i.e., the digit 1.
• Step 3: Remove 1. Remaining digits: 8, 6, 7, 0. Sum = 21, which is divisible by 3.
• Step 4: Arrange in descending order: 8, 7, 6, 0. Result: "8760".

Time and Space Complexity

• Brute-force Approach: Generating all combinations and permutations is exponential: O(2ⁿ * n!), which is infeasible for large n.
• Optimized Approach: Counting digits and sum is O(n). Removing digits is O(1) (since there are only 10 possible digits). Sorting or arranging digits in descending order is O(n log n), but since we use counting sort (by traversing from 9 to 0), this is effectively O(n).
• Space Complexity: O(n) for storing the result, O(1) for digit counts (fixed size array).

Thus, the optimized solution is linear in time and space with respect to the input size.

Summary

The key insight is that divisibility by three depends only on the sum of the digits. By counting digits and removing the minimal set necessary to achieve a sum divisible by three, we can efficiently construct the largest possible number. Arranging the remaining digits in descending order ensures the result is as large as possible. This approach is both elegant and efficient, leveraging mathematical properties and simple data structures to solve the problem optimally.