# Largest Multiple of Three
**Difficulty:** HARD
[External](https://leetcode.com/problems/largest-multiple-of-three)
Canonical: https://scaleengineer.com/dsa/problems/largest-multiple-of-three
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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 <= 104`
* `0 <= digits[i] <= 9`

# Approaches
## Sorting and Grouping by Remainder
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.
**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.
**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.
### Explanation
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        List<Integer> rem0 = new ArrayList<>();
        List<Integer> rem1 = new ArrayList<>();
        List<Integer> rem2 = new ArrayList<>();
        int sum = 0;

        for (int digit : digits) {
            sum += digit;
            if (digit % 3 == 0) {
                rem0.add(digit);
            } else if (digit % 3 == 1) {
                rem1.add(digit);
            } else {
                rem2.add(digit);
            }
        }

        Collections.sort(rem1);
        Collections.sort(rem2);

        if (sum % 3 == 1) {
            if (!rem1.isEmpty()) {
                rem1.remove(0); // Remove smallest from rem1
            } else if (rem2.size() >= 2) {
                rem2.remove(0);
                rem2.remove(0); // Remove two smallest from rem2
            } else {
                return ""; // Cannot make sum divisible by 3
            }
        } else if (sum % 3 == 2) {
            if (!rem2.isEmpty()) {
                rem2.remove(0); // Remove smallest from rem2
            } else if (rem1.size() >= 2) {
                rem1.remove(0);
                rem1.remove(0); // Remove two smallest from rem1
            } else {
                return ""; // Cannot make sum divisible by 3
            }
        }

        List<Integer> resultList = Stream.of(rem0, rem1, rem2)
                                         .flatMap(List::stream)
                                         .collect(Collectors.toList());
        
        Collections.sort(resultList, Collections.reverseOrder());

        if (resultList.isEmpty()) {
            return "";
        }

        // If the largest digit is 0, the result should be "0"
        if (resultList.get(0) == 0) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for (int digit : resultList) {
            sb.append(digit);
        }

        return sb.toString();
    }
}
```
### Algorithm
1. The core principle is that a number is divisible by 3 if and only if the sum of its digits is divisible by 3.
2. To form the largest possible number, we should use as many digits as possible and arrange them in descending order.
3. Calculate the sum of all digits in the input array.
4. Group the digits into three separate lists based on their remainder when divided by 3: `rem0`, `rem1`, and `rem2`.
5. Sort the `rem1` and `rem2` lists in ascending order. This makes it easy to find and remove the smallest digits if necessary.
6. 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.
7. After the potential removals, combine all remaining digits from `rem0`, `rem1`, and `rem2` into a single list.
8. Sort this final list in descending order.
9. Build the result string from the sorted list.
10. Handle edge cases: If the resulting number is empty, return `""`. If the number is composed of only zeros (e.g., `"000"`), return `"0"`.

## Optimal Approach with Frequency Counting
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.
**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.
**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.
### Explanation
```java
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;
    }
}
```
### Algorithm
1. Instead of storing digits in lists, use a frequency array `counts` of size 10 to store the count of each digit (0-9).
2. Iterate through the input `digits` once to populate the `counts` array and calculate the total `sum`.
3. Determine the remainder `rem = sum % 3`.
4. 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).
5. The removals are done by decrementing the values in the `counts` array.
6. 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.
7. 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"`.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string largestMultipleOfThree(vector<int> &digits) {
    sort(digits.begin(), digits.end());
    int n = digits.size();
    int f[n + 1][3];
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 3; ++j) {
        f[i][j] =
            max(f[i - 1][j], f[i - 1][(j - digits[i - 1] % 3 + 3) % 3] + 1);
      }
    }
    if (f[n][0] <= 0) {
      return "";
    }
    string ans;
    for (int i = n, j = 0; i; --i) {
      int k = (j - digits[i - 1] % 3 + 3) % 3;
      if (f[i - 1][k] + 1 == f[i][j]) {
        ans += digits[i - 1] + '0';
        j = k;
      }
    }
    int i = 0;
    while (i < ans.size() - 1 && ans[i] == '0') {
      ++i;
    }
    return ans.substr(i);
  }
};

```

### Python

```python
class Solution:
    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:]))

```