Largest Multiple of Three

Hard

#1265Time: 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.

Patterns

Math Dynamic Programming Greedy

Algorithms

Sorting

Data structures

Array

Prompt

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 <= 10⁴
0 <= 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 counts of size 10 to store the count of each digit (0-9).
Iterate through the input digits once to populate the counts array and calculate the total sum.
Determine the remainder rem = sum % 3.
If rem is 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 digit d where d % 3 == 1 (checking 1, then 4, then 7). If this is not possible, we must remove two digits d where d % 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 digit d where d % 3 == 2 (checking 2, then 5, then 8). If not possible, we remove two digits d where d % 3 == 1 (checking for two from 1, 4, 7).
The removals are done by decrementing the values in the counts array.
After the counts array is finalized, build the result string. Iterate from i = 9 down to 0, appending the digit i to the result counts[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

1class Solution {2    public String largestMultipleOfThree(int[] digits) {3        int[] counts = new int[10];4        int sum = 0;5        for (int d : digits) {6            counts[d]++;7            sum += d;8        }9 10        int rem = sum % 3;11 12        if (rem != 0) {13            // We need to remove digits to make the sum divisible by 314            if (rem == 1) {15                // Try to remove one digit with rem 1, else two digits with rem 216                if (!remove(counts, 1)) {17                    remove(counts, 2);18                    remove(counts, 2);19                }20            } else { // rem == 221                // Try to remove one digit with rem 2, else two digits with rem 122                if (!remove(counts, 2)) {23                    remove(counts, 1);24                    remove(counts, 1);25                }26            }27        }28 29        StringBuilder sb = new StringBuilder();30        for (int i = 9; i >= 0; i--) {31            for (int j = 0; j < counts[i]; j++) {32                sb.append(i);33            }34        }35 36        String result = sb.toString();37        if (result.length() > 0 && result.charAt(0) == '0') {38            return "0";39        }40 41        return result;42    }43 44    // Tries to remove one smallest digit `d` such that `d % 3 == rem`45    // Returns true if a digit was successfully removed, false otherwise.46    private boolean remove(int[] counts, int rem) {47        for (int i = rem; i < 10; i += 3) {48            if (counts[i] > 0) {49                counts[i]--;50                return true;51            }52        }53        return false;54    }55}

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.

This approach is based on the number theory property that a number's divisibility by three is determined by the sum of its digits. The goal is to select a subset of the given digits whose sum is a multiple of three, and then arrange them to form the largest possible number.

First, we calculate the sum of all available digits. If this sum is already a multiple of three, we can use all digits. If not, the sum's remainder modulo 3 will be either 1 or 2. To make the sum of our chosen digits a multiple of three, we must discard some digits. To maximize the final number, we should discard as few digits as possible, and among those, the ones with the smallest value.

We segregate the digits into three groups based on their remainder (0, 1, or 2) when divided by 3. This allows us to easily identify which digits to remove based on the total sum's remainder. After removing the necessary digits, we collect all the remaining ones, sort them in descending order, and form the result string.

Algorithm

The core principle is that a number is divisible by 3 if and only if the sum of its digits is divisible by 3.
To form the largest possible number, we should use as many digits as possible and arrange them in descending order.
Calculate the sum of all digits in the input array.
Group the digits into three separate lists based on their remainder when divided by 3: rem0, rem1, and rem2.
Sort the rem1 and rem2 lists in ascending order. This makes it easy to find and remove the smallest digits if necessary.
Check the remainder of the total sum modulo 3 (sum % 3):
- If sum % 3 == 1: We need to remove a total remainder of 1. The best way to do this while keeping the most digits is to either remove one digit with a remainder of 1, or two digits with a remainder of 2. We prioritize removing one digit. So, if the rem1 list is not empty, we remove its smallest element. Otherwise, we remove the two smallest elements from the rem2 list.
- If sum % 3 == 2: Similarly, we need to remove a total remainder of 2. We prioritize removing one digit with a remainder of 2. If the rem2 list is not empty, we remove its smallest element. Otherwise, we remove the two smallest elements from the rem1 list.
After the potential removals, combine all remaining digits from rem0, rem1, and rem2 into a single list.
Sort this final list in descending order.
Build the result string from the sorted list.
Handle edge cases: If the resulting number is empty, return "". If the number is composed of only zeros (e.g., "000"), return "0".

Walkthrough

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4import java.util.stream.Collectors;5import java.util.stream.Stream;6 7class Solution {8    public String largestMultipleOfThree(int[] digits) {9        List<Integer> rem0 = new ArrayList<>();10        List<Integer> rem1 = new ArrayList<>();11        List<Integer> rem2 = new ArrayList<>();12        int sum = 0;13 14        for (int digit : digits) {15            sum += digit;16            if (digit % 3 == 0) {17                rem0.add(digit);18            } else if (digit % 3 == 1) {19                rem1.add(digit);20            } else {21                rem2.add(digit);22            }23        }24 25        Collections.sort(rem1);26        Collections.sort(rem2);27 28        if (sum % 3 == 1) {29            if (!rem1.isEmpty()) {30                rem1.remove(0); // Remove smallest from rem131            } else if (rem2.size() >= 2) {32                rem2.remove(0);33                rem2.remove(0); // Remove two smallest from rem234            } else {35                return ""; // Cannot make sum divisible by 336            }37        } else if (sum % 3 == 2) {38            if (!rem2.isEmpty()) {39                rem2.remove(0); // Remove smallest from rem240            } else if (rem1.size() >= 2) {41                rem1.remove(0);42                rem1.remove(0); // Remove two smallest from rem143            } else {44                return ""; // Cannot make sum divisible by 345            }46        }47 48        List<Integer> resultList = Stream.of(rem0, rem1, rem2)49                                         .flatMap(List::stream)50                                         .collect(Collectors.toList());51        52        Collections.sort(resultList, Collections.reverseOrder());53 54        if (resultList.isEmpty()) {55            return "";56        }57 58        // If the largest digit is 0, the result should be "0"59        if (resultList.get(0) == 0) {60            return "0";61        }62 63        StringBuilder sb = new StringBuilder();64        for (int digit : resultList) {65            sb.append(digit);66        }67 68        return sb.toString();69    }70}

Complexity

Time

O(N log N), where N is the number of digits. The dominant operations are sorting the remainder lists (which can be up to O(N log N) in the worst case) and sorting the final combined list.

Space

O(N), where N is the number of digits. This space is used to store the three lists for remainders.

Trade-offs

Pros

The logic is intuitive and directly follows from the mathematical property of divisibility by three.
It correctly solves the problem for all valid inputs.

Cons

The time complexity is not optimal due to multiple sorting operations.
It uses extra space proportional to the input size to store the groups of digits.

Solutions

Solution

1class Solution {2public3  String largestMultipleOfThree(int[] digits) {4    Arrays.sort(digits);5    int n = digits.length;6    int[][] f = new int[n + 1][3];7    final int inf = 1 << 30;8    for (var g : f) {9      Arrays.fill(g, -inf);10    }11    f[0][0] = 0;12    for (int i = 1; i <= n; ++i) {13      for (int j = 0; j < 3; ++j) {14        f[i][j] = Math.max(f[i - 1][j],15                           f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1);16      }17    }18    if (f[n][0] <= 0) {19      return "";20    }21    StringBuilder sb = new StringBuilder();22    for (int i = n, j = 0; i > 0; --i) {23      int k = (j - digits[i - 1] % 3 + 3) % 3;24      if (f[i - 1][k] + 1 == f[i][j]) {25        sb.append(digits[i - 1]);26        j = k;27      }28    }29    int i = 0;30    while (i < sb.length() - 1 && sb.charAt(i) == '0') {31      ++i;32    }33    return sb.substring(i);34  }35}

1class Solution {2public:3  string largestMultipleOfThree(vector<int> &digits) {4    sort(digits.begin(), digits.end());5    int n = digits.size();6    int f[n + 1][3];7    memset(f, -0x3f, sizeof(f));8    f[0][0] = 0;9    for (int i = 1; i <= n; ++i) {10      for (int j = 0; j < 3; ++j) {11        f[i][j] =12            max(f[i - 1][j], f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1);13      }14    }15    if (f[n][0] <= 0) {16      return "";17    }18    string ans;19    for (int i = n, j = 0; i; --i) {20      int k = (j - digits[i - 1] % 3 + 3) % 3;21      if (f[i - 1][k] + 1 == f[i][j]) {22        ans += digits[i - 1] + '0';23        j = k;24      }25    }26    int i = 0;27    while (i < ans.size() - 1 && ans[i] == '0') {28      ++i;29    }30    return ans.substr(i);31  }32};

1class Solution:2    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:]))

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.

← Previous

Previous problem

Next problem