Biggest Multiple of Three From Digit Tiles
Problem
A puzzle box holds tiles, each printed with one decimal digit digits[i]. You may pick any subset of the tiles and arrange them to read a number. The number must be divisible by 3.
Return the largest such number as a string, without leading zeros (a number made only of zeros is "0"). If no non-empty subset works, return the empty string "".
Example 1
- Input:
- digits = [8, 6, 7, 1, 0]
- Output:
- "8760"
The digit sum 22 leaves remainder 1 mod 3; dropping the single tile 1 leaves 21, and 8760 is the largest arrangement.
Example 2
- Input:
- digits = [8, 1, 9]
- Output:
- "981"
Example 3
- Input:
- digits = [5, 8]
- Output:
- ""
No non-empty subset has a digit sum divisible by 3.
Constraints
- 1 ≤ digits.length ≤ 10^4
- 0 ≤ digits[i] ≤ 9
Hint
Show the first hint
A number is divisible by 3 exactly when its digit sum is. And for a fixed set of tiles, the biggest arrangement is the digits in descending order.
Walkthrough
How to approach it
01Clarify before coding
- Must all tiles be used? No, any non-empty subset.
- What if the best number is zero? Return "0", not "000".
- What if nothing works? Return the empty string.
02Brute force
Try every subset, keep those with digit sum divisible by 3, sort each descending and keep the largest.
Cost: O(2^n · n): hopeless beyond about 20 tiles.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.