Largest Multiple of Three
HardPrompt
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] <= 9
Approaches
2 approaches with complexity analysis and trade-offs.
This optimal approach enhances the previous method by eliminating the need for sorting, which reduces the time complexity from O(N log N) to O(N). It leverages a frequency map (an array of size 10) to count the occurrences of each digit. This is a form of counting sort.
The core logic remains the same: calculate the sum of digits, find its remainder modulo 3, and remove the minimum number of smallest-valued digits to make the sum a multiple of 3. However, instead of manipulating lists of digits, we simply decrement the counts in our frequency array. For example, to remove the smallest digit with a remainder of 1, we check counts[1], then counts[4], then counts[7] and decrement the first one we find.
After adjusting the counts, we can construct the final, largest number by iterating through our frequency array from 9 down to 0 and appending each digit the number of times it appears. This avoids a final sorting step and is highly efficient.
Algorithm
- Instead of storing digits in lists, use a frequency array
countsof size 10 to store the count of each digit (0-9). - Iterate through the input
digitsonce to populate thecountsarray and calculate the totalsum. - Determine the remainder
rem = sum % 3. - If
remis not 0, we must remove certain digits to make the new sum divisible by 3. The goal is to remove the smallest valued digits that satisfy the condition.- If
rem == 1: We need to remove a total remainder of 1. We first try to remove one digitdwhered % 3 == 1(checking 1, then 4, then 7). If this is not possible, we must remove two digitsdwhered % 3 == 2(checking for two from 2, 5, 8). - If
rem == 2: We need to remove a total remainder of 2. We first try to remove one digitdwhered % 3 == 2(checking 2, then 5, then 8). If not possible, we remove two digitsdwhered % 3 == 1(checking for two from 1, 4, 7).
- If
- The removals are done by decrementing the values in the
countsarray. - After the
countsarray is finalized, build the result string. Iterate fromi = 9down to0, appending the digitito the resultcounts[i]times. This naturally creates the largest number without explicit sorting. - Handle edge cases: If the result string is empty, return
"". If it's not empty and starts with '0' (meaning all remaining digits are 0), return"0".
Walkthrough
class Solution { public String largestMultipleOfThree(int[] digits) { int[] counts = new int[10]; int sum = 0; for (int d : digits) { counts[d]++; sum += d; } int rem = sum % 3; if (rem != 0) { // We need to remove digits to make the sum divisible by 3 if (rem == 1) { // Try to remove one digit with rem 1, else two digits with rem 2 if (!remove(counts, 1)) { remove(counts, 2); remove(counts, 2); } } else { // rem == 2 // Try to remove one digit with rem 2, else two digits with rem 1 if (!remove(counts, 2)) { remove(counts, 1); remove(counts, 1); } } } StringBuilder sb = new StringBuilder(); for (int i = 9; i >= 0; i--) { for (int j = 0; j < counts[i]; j++) { sb.append(i); } } String result = sb.toString(); if (result.length() > 0 && result.charAt(0) == '0') { return "0"; } return result; } // Tries to remove one smallest digit `d` such that `d % 3 == rem` // Returns true if a digit was successfully removed, false otherwise. private boolean remove(int[] counts, int rem) { for (int i = rem; i < 10; i += 3) { if (counts[i] > 0) { counts[i]--; return true; } } return false; }}Complexity
Time
O(N), where N is the number of digits. We iterate through the digits once to populate the counts. The removal and string-building steps take constant time with respect to N.
Space
O(1), as the space used for the `counts` array is constant (size 10) and does not depend on the input size N.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Extremely efficient for large inputs as it avoids all sorting operations.
Cons
The logic for removing digits from the frequency map can be slightly more intricate to implement correctly compared to removing from sorted lists.
Solutions
Solution
class Solution {public String largestMultipleOfThree(int[] digits) { Arrays.sort(digits); int n = digits.length; int[][] f = new int[n + 1][3]; final int inf = 1 << 30; for (var g : f) { Arrays.fill(g, -inf); } f[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 3; ++j) { f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1); } } if (f[n][0] <= 0) { return ""; } StringBuilder sb = new StringBuilder(); for (int i = n, j = 0; i > 0; --i) { int k = (j - digits[i - 1] % 3 + 3) % 3; if (f[i - 1][k] + 1 == f[i][j]) { sb.append(digits[i - 1]); j = k; } } int i = 0; while (i < sb.length() - 1 && sb.charAt(i) == '0') { ++i; } return sb.substring(i); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.