Largest Multiple of Three — Hard Problem & Solution

Given an array of digits, concatenate some of them (in any order, using each at most as many times as it appears) to form the largest possible number that…

Difficulty: Hard
Topics: Arrays, Math, Dynamic Programming, Greedy
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of digits, concatenate some of them (in any order, using each at most as many times as it appears) to form the largest possible number that is divisible by three.

Return it as a string without leading zeros, or "0" if the best answer is zero, or the empty string if no multiple of three can be formed.

Example 1

Input: digits = [8,1,9]
Output: 981
Explanation: 8 + 1 + 9 = 18 is already divisible by 3, so use every digit in descending order.

Example 2

Input: digits = [8,6,7,1,0]
Output: 8760
Explanation: The total is 22; dropping the 1 makes it 21 and leaves the largest arrangement.

Example 3

Input: digits = [1]
Output: 
Explanation: Nothing can be formed.

Constraints

1 <= digits.length <= 10000
0 <= digits[i] <= 9

How to solve Largest Multiple of Three

Divisibility depends only on the multiset of digits, while size depends first on how many digits survive and then on their descending order. So delete as few digits as possible — and among those, the smallest ones.

Approach

Tally the digits and compute the total sum; let r = sum % 3.
If r != 0, try deleting one digit congruent to r modulo 3, scanning r, r+3, r+6 so the smallest goes first.
If there is none, delete two digits congruent to 3 - r, again smallest first. If two cannot be found, return "".
Emit the remaining digits from 9 down to 0; if the result is empty return "", and if it starts with 0 the answer is "0".

Why it works

Deleting one digit beats deleting two, and within a fixed deletion count the surviving number is largest when the deleted digits are smallest and the survivors are sorted descending. One deletion congruent to r or two congruent to 3 - r are the only ways to shift the remainder to zero while removing at most two digits, and removing three or more is never necessary when either option exists.

Complexity

Time — O(n + 10)
Space — O(10)

Pitfalls

Deleting the largest matching digit shrinks the answer unnecessarily.
A leading zero means every surviving digit is zero, which must collapse to "0" rather than "000".
Sorting the whole array is fine but a 10-slot tally is both simpler and faster.

Reference solution

Python

from typing import List

def largestMultipleOfThree(digits: List[int]) -> str:
    count = [0] * 10
    total = 0
    for d in digits:
        count[d] += 1
        total += d
    r = total % 3
    if r != 0:
        removed = False
        for d in range(r, 10, 3):
            if count[d] > 0:
                count[d] -= 1
                removed = True
                break
        if not removed:
            need = 2
            for d in range((3 - r) % 3, 10, 3):
                while count[d] > 0 and need > 0:
                    count[d] -= 1
                    need -= 1
            if need > 0:
                return ""
    out = "".join(str(d) * count[d] for d in range(9, -1, -1))
    if not out:
        return ""
    if out[0] == "0":
        return "0"
    return out

JavaScript

var largestMultipleOfThree = function(digits) {
    var count = [];
    for (var t = 0; t < 10; t++) count.push(0);
    var sum = 0;
    for (var i = 0; i < digits.length; i++) { count[digits[i]]++; sum += digits[i]; }
    var r = sum % 3;
    if (r !== 0) {
        var removed = false;
        for (var d = r; d <= 9; d += 3) {
            if (count[d] > 0) { count[d]--; removed = true; break; }
        }
        if (!removed) {
            var need = 2;
            for (var e = (3 - r) % 3; e <= 9 && need > 0; e += 3) {
                while (count[e] > 0 && need > 0) { count[e]--; need--; }
            }
            if (need > 0) return "";
        }
    }
    var out = "";
    for (var g = 9; g >= 0; g--) {
        for (var k = 0; k < count[g]; k++) out += String(g);
    }
    if (out.length === 0) return "";
    if (out.charAt(0) === "0") return "0";
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue