Largest Multiple of Three: Greedy Digit-Sum Modular Arithmetic

Given an array of digits (0 through 9), find the largest multiple of three that can be formed by concatenating some or all of the digits in any order. If no multiple of three can be formed, return an empty string. If the result is zero, return "0".

This is LeetCode 1363: Largest Multiple of Three, a hard problem that becomes surprisingly clean once you recognize the connection between digit sums and divisibility by 3. The trick is not to try every combination. Instead, you sort the digits, check the total sum mod 3, and greedily remove at most two of the smallest digits to fix the remainder.

Why this problem matters

This problem tests whether you can combine two ideas: a number theory fact (a number is divisible by 3 if and only if its digit sum is divisible by 3) with a greedy removal strategy. Many candidates jump to dynamic programming or brute-force subset enumeration, but neither is necessary. The greedy approach runs in O(n log n) time and handles all the edge cases cleanly.

The pattern of "sort, then selectively remove the minimum to satisfy a constraint" shows up across many greedy problems. Mastering it here gives you a template for problems where you want to maximize a result while satisfying a divisibility or modular constraint.

The key insight

A number is divisible by 3 if and only if the sum of its digits is divisible by 3. This means you do not need to check every possible concatenation. You just need to look at the digit sum.

If the digit sum mod 3 is already 0, keep all digits. If the remainder is 1, you have two choices: remove one digit whose remainder is 1, or remove two digits whose remainders are each 2. If the remainder is 2, the mirror applies: remove one digit with remainder 2, or two digits with remainder 1. In every case, you pick the option that removes the fewest and smallest digits, keeping the result as large as possible.

The solution

def largestMultipleOfThree(digits):
    digits.sort(reverse=True)
    buckets = [[], [], []]
    for d in digits:
        buckets[d % 3].append(d)

    total = sum(digits)
    rem = total % 3

    if rem == 1:
        if buckets[1]:
            buckets[1].pop()
        elif len(buckets[2]) >= 2:
            buckets[2].pop()
            buckets[2].pop()
        else:
            return ""
    elif rem == 2:
        if buckets[2]:
            buckets[2].pop()
        elif len(buckets[1]) >= 2:
            buckets[1].pop()
            buckets[1].pop()
        else:
            return ""

    result = sorted(buckets[0] + buckets[1] + buckets[2], reverse=True)

    if not result:
        return ""
    if result[0] == 0:
        return "0"
    return "".join(map(str, result))

The algorithm works in three phases. First, sort the digits in descending order and place each digit into one of three buckets based on its remainder mod 3. Second, check the total digit sum mod 3. If the remainder is not zero, remove the smallest possible digits to fix it. Since each bucket was built from a descending-sorted list, the smallest digit in a bucket is always at the end, so pop() removes the right one. Third, merge the remaining digits, sort them descending again, and build the result string.

The reason we prefer removing one digit over two is simple: fewer removals means more digits in the result, which means a larger number. And within each removal option, we always remove the smallest available digit because that has the least impact on the final value.

Visual walkthrough

Complexity analysis

The sorting-based approach dominates the runtime at O(n log n). If you replace the sort with a counting sort (since digits are 0 through 9, there are only 10 possible values), you can bring the time down to O(n) and the space to O(1). The logic stays exactly the same; only the sorting step changes.

The building blocks

1. Digit sum divisibility rule

The mathematical foundation is that a number's remainder mod 3 equals the sum of its digits mod 3. This rule applies because 10 is congruent to 1 mod 3, so 10^k is also congruent to 1 mod 3 for all k. That means each digit d in position k contributes d * 1 = d to the total mod 3.

This same principle works for divisibility by 9 (digit sum mod 9), and the general idea of using modular arithmetic to reduce a problem over large numbers to a problem over small remainders appears throughout competitive programming and interview questions.

2. Greedy removal strategy

When you need to keep a result as large as possible while satisfying a constraint, the greedy approach is to remove the minimum number of the smallest elements. Here, "minimum number" means preferring to remove one digit over two, and "smallest" means choosing the digit with the least value from the relevant remainder bucket.

This greedy removal pattern shows up in problems like Remove K Digits (remove k digits to minimize the number) and in scheduling problems where you drop the least valuable items to meet a budget. The key requirement is that removing a smaller element is always better than removing a larger one, which holds here because every remaining digit occupies a decimal position and a larger digit always contributes more.

Edge cases

Before submitting, make sure your solution handles these:

• All zeros [0, 0, 0]: the sum is 0 (divisible by 3), but the result should be "0", not "000". Check if the leading digit is 0 after building the result.
• No valid multiple [1, 1]: sum is 2, remainder is 2. No digit has remainder 2, and you cannot remove two digits with remainder 1 (that would leave nothing). Return "".
• Single digit divisible by 3 [9]: the answer is "9". No removal needed.
• Single digit not divisible by 3 [5]: sum mod 3 = 2. Removing it leaves nothing. Return "".
• Digits that require removing two [2, 2, 1, 1, 1]: sum = 7, remainder = 1. Removing one digit with remainder 1 gives [2, 2, 1, 1], sum = 6. Result = "2211".
• Large input with many zeros [0, 0, 0, 1, 2]: sum = 3, remainder = 0. Keep all digits. Result = "21000".

From understanding to recall

You have read the greedy solution and it makes sense. Sort, bucket by remainder, check the sum, remove at most two digits, done. But can you write it from scratch in an interview without looking at it?

The details matter: remembering to sort descending so pop gives the smallest, handling the two removal paths (one digit vs. two), and catching the all-zeros edge case. These are the kinds of things that trip you up under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the bucket-and-remove logic from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "largest number divisible by 3" and the code flows out without hesitation.

The digit-sum divisibility rule and greedy removal strategy are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Largest Number - Another problem about forming the largest possible number from an array, using a custom sort comparator
• Gas Station - Greedy single-pass problem where you reset a candidate when a running total goes negative
• Candy - Two-pass greedy that satisfies constraints from both directions
• Remove K Digits - Greedy digit removal using a monotonic stack to minimize a number
• Sort Colors - Bucket-based partitioning, similar to grouping digits by remainder

CodeBricks breaks the largest multiple of three LeetCode problem into its digit-sum divisibility and greedy removal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy modular arithmetic question shows up in your interview, you do not think about it. You just write it.