Given an array of digits digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. If there is no answer return an empty string.
Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.
Example 1:
Input: digits = [8,1,9] Output: "981"
Example 2:
Input: digits = [8,6,7,1,0] Output: "8760"
Example 3:
Input: digits = [1] Output: ""
Constraints:
1 <= digits.length <= 1040 <= digits[i] <= 9Problem Overview: You are given an array of digits (0–9). Rearrange some or all digits to form the largest possible integer that is divisible by 3. If no such number exists, return an empty string. The key constraint comes from divisibility rules: a number is divisible by 3 when the sum of its digits is divisible by 3.
Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)
This approach uses a greedy idea based on the divisibility rule of 3. First, sort the digits in ascending order so you can easily remove the smallest digits when adjustments are needed. Compute the total digit sum and check sum % 3. If the remainder is 1, remove the smallest digit with remainder 1; otherwise remove two digits with remainder 2. If the remainder is 2, remove the smallest digit with remainder 2 or two digits with remainder 1. After removal, sort the remaining digits in descending order to form the largest possible number.
The greedy insight is that removing the smallest possible digits preserves the maximum value of the final number. Sorting helps you quickly identify candidates for removal and construct the final result. Time complexity is O(n log n) due to sorting, and space complexity is O(n) for storing digits. This method works well when you want a straightforward implementation using basic array operations and greedy reasoning.
Approach 2: Digit Counting and Modulo Manipulation (O(n) time, O(1) space)
This approach avoids sorting by counting occurrences of each digit (0–9). First compute the sum of all digits and determine sum % 3. Maintain counts of digits grouped by their modulo with 3. If the remainder is 1, remove the smallest digit whose value % 3 == 1; if none exist, remove two digits whose value % 3 == 2. If the remainder is 2, remove the smallest digit whose value % 3 == 2, or two digits whose value % 3 == 1.
After adjusting the counts, reconstruct the result by iterating from digit 9 down to 0 and appending digits according to their frequency. Because digit range is fixed (0–9), counting and reconstruction run in linear time relative to the input size. Time complexity is O(n) and space complexity is O(1) since the digit frequency array has constant size. This technique combines greedy selection with modulo arithmetic and is often discussed alongside dynamic programming-style remainder reasoning, though the final implementation is purely greedy.
Recommended for interviews: The digit counting and modulo manipulation approach is typically the expected optimal solution. Interviewers want to see that you recognize the divisibility-by-3 rule and adjust the digit set greedily while preserving the largest lexicographic order. Starting with the sorting-based greedy solution shows clear reasoning, while the counting optimization demonstrates stronger algorithmic insight and reduces the complexity to O(n).
This approach involves sorting the digits in descending order to form the largest number possible and checking its divisibility by 3.
1. Compute the sum of all the digits to determine if the whole number is divisible by 3.
2. If the sum % 3 == 0, the digits form a valid multiple of 3; otherwise, remove the smallest number of digits to make it divisible by 3.
The key is to strategically remove digits with minimal impact on the resulting number’s magnitude by leveraging sorting and divisibility rules.
Sort digits in descending order to form the largest number possible. Check if the sum of the digits is divisible by 3. If not, attempt to remove digits minimally to make the sum divisible by 3.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting can be done in-place.
In this approach, rather than sorting, we leverage digit frequency and modulo properties to construct the number that is a multiple of three.
1. Count the frequency of each digit.
2. Calculate the sum of the digits.
3. Depending on sum % 3, remove the minimal digits based on their digital value to correct the sum to be divisible by 3.
Calculate the sum of digits, and adjust by removing the least significant digits with appropriate modulo to ensure divisibility by 3.
Time Complexity: O(n), since we have to pass through the array elements a few times without sorting.
Space Complexity: O(1), utilizes fixed utility space to construct numbers.
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.
Consider how f[i][j] transitions. We can choose not to select the i-th number, in which case f[i][j] = f[i - 1][j]; we can also choose to select the i-th number, in which case f[i][j] = f[i - 1][(j - x_i bmod 3 + 3) bmod 3] + 1, where x_i represents the value of the i-th number. Therefore, we have the following state transition equation:
$
f[i][j] = max { f[i - 1][j], f[i - 1][(j - x_i bmod 3 + 3) bmod 3] + 1 }
If f[n][0] \le 0, then we cannot select any number, so the answer string is empty. Otherwise, we can backtrack through the f array to find out the selected numbers.
Define i = n, j = 0, start backtracking from f[i][j], let k = (j - x_i bmod 3 + 3) bmod 3, if f[i - 1][k] + 1 = f[i][j], then we have selected the i-th number, otherwise we have not selected the i-th number. If we have selected the i-th number, then we update j to k, otherwise we keep j unchanged. To make the number of the same length as large as possible, we should prefer to select larger numbers, so we should sort the array first.
The time complexity is O(n times log n), and the space complexity is O(n). Where n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as sorting can be done in-place. |
| Digit Counting and Modulo Manipulation | Time Complexity: O(n), since we have to pass through the array elements a few times without sorting. Space Complexity: O(1), utilizes fixed utility space to construct numbers. |
| Greedy + Dynamic Programming + Backtracking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(n) | Best for a straightforward implementation using sorting and simple greedy removal logic. |
| Digit Counting and Modulo Manipulation | O(n) | O(1) | Optimal approach when you want linear time by avoiding sorting and using digit frequency counting. |
Largest Multiple of Three || Leetcode • Pepcoding • 5,750 views views
Watch 9 more video solutions →Practice Largest Multiple of Three with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor