Start by computing the sum of all digits and classify them by modulo three categories to track possible remainders. Use state transition dynamic programming to determine which digits to remove to maximize the final number. Return digits sorted in descending order as a string without leading zeros, ensuring the largest multiple of three is constructed correctly.
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.
How GhostInterview Helps
- GhostInterview identifies which digits to remove using the state transition dynamic programming pattern efficiently.
- It simulates remainder grouping and sums to verify the largest possible multiple of three in real time.
- Provides immediate feedback on sorting and concatenation issues that could reduce the final number.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Largest Multiple of Three instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Largest Multiple of Three from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the maximum sum divisible by three from a given array using dynamic programming and state transition.
Open problem page#1648 Sell Diminishing-Valued Colored BallsMaximize total value by greedily selling diminishing-valued colored balls based on inventory and customer orders.
Open problem page#646 Maximum Length of Pair ChainDetermine the maximum length of a chain formed by pairs using dynamic programming and greedy sorting techniques efficiently.
Open problem page