#1363

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Largest Multiple of Three

Find the largest number divisible by three by selecting and ordering digits optimally using state transition dynamic programming techniques.

array math dynamic programming greedy sorting

Problem Statement

You are given an array of digits. Your task is to form the largest possible number that is a multiple of three by concatenating some or all digits in any order. If no such number can be formed, return an empty string. The final number must not contain unnecessary leading zeros, and must be returned as a string.

Constraints include handling up to 10,000 digits with values from 0 to 9. Focus on applying state transition dynamic programming to manage digit removal based on their modulo three remainder, and sort the remaining digits to maximize the resulting number.

Examples

Example 1

Input: digits = [8,1,9]

Output: "981"

Example details omitted.

Example 2

Input: digits = [8,6,7,1,0]

Output: "8760"

Example details omitted.

Example 3

Input: digits = [1]

Output: ""

Example details omitted.

Constraints

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

Solution Approach

Classify digits by remainder modulo three

Divide digits into three groups based on their value modulo three. Track counts for digits where value % 3 == 0, 1, or 2. This categorization is key to applying state transitions efficiently to find combinations summing to multiples of three.

Adjust digits using state transitions

Compute the total sum of digits and determine its remainder modulo three. If the remainder is non-zero, remove the minimum number of digits needed from appropriate groups to make the sum divisible by three. This is where the state transition dynamic programming pattern ensures optimal choices.

Construct the final number

Sort the remaining digits in descending order and concatenate them to form the largest number. Handle edge cases like all zeros to avoid leading zeros. The final string represents the maximum multiple of three achievable from the input array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k log k) where n is the number of digits and k is the remaining digits after removal, mainly due to sorting. Space complexity is O(n) for storing grouped digits and intermediate states required by the state transition dynamic programming approach.

What Interviewers Usually Probe

Check if the sum of digits modulo three is zero to quickly identify multiples of three.
Consider edge cases with many zeros or a single digit that cannot form a multiple of three.
Verify your state transitions correctly remove minimal digits to maximize the final number.

Common Pitfalls or Variants

Common pitfalls

Failing to remove the smallest number of digits needed, resulting in suboptimal output.
Leaving unnecessary leading zeros in the final string.
Ignoring digits classification by modulo three, which breaks the dynamic programming logic.

Follow-up variants

Find the smallest multiple of three instead of the largest, adjusting sorting strategy.
Return the largest multiple of five from digits using similar state transition reasoning.
Compute the largest multiple of k for any k using remainder-based dynamic programming extensions.

FAQ

What is the main pattern used in Largest Multiple of Three?

The primary pattern is state transition dynamic programming, applied to digit groups modulo three to select removals optimally.

Can the input array contain zeros only?

Yes, but the largest multiple of three in that case is simply "0" without additional digits or leading zeros.

How do I handle single-digit arrays that are not multiples of three?

Return an empty string since no combination can form a multiple of three.

Is sorting necessary in this solution?

Yes, sorting the remaining digits in descending order ensures the largest number is formed after state transitions.

Why does GhostInterview emphasize remainder classification?

Classifying digits by remainder modulo three allows efficient state transitions to remove minimal digits and maximize the final multiple of three.

terminal

Solution

Solution 1: Greedy + Dynamic Programming + Backtracking

We define $f[i][j]$ as the maximum length of selecting several numbers from the first $i$ numbers, so that the sum of the selected numbers modulo $3$ equals $j$. To make the selected numbers as large as possible, we need to select as many numbers as possible, so we need to make $f[i][j]$ as large as possible. We initialize $f[0][0] = 0$, and the rest of $f[0][j] = -\infty$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort()
        n = len(digits)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(digits, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + 1)
        if f[n][0] <= 0:
            return ""
        arr = []
        j = 0
        for i in range(n, 0, -1):
            k = (j - digits[i - 1] % 3 + 3) % 3
            if f[i - 1][k] + 1 == f[i][j]:
                arr.append(digits[i - 1])
                j = k
        i = 0
        while i < len(arr) - 1 and arr[i] == 0:
            i += 1
        return "".join(map(str, arr[i:]))

Continue Practicing

#1262 greatest sum divisible by three #1648 sell diminishing valued colored balls #646 maximum length of pair chain