> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/1363.-largest-multiple-of-three.md).

# 1363. Largest Multiple of Three

https\://leetcode.com/problems/largest-multiple-of-three/

Given an integer array of `digits`, return the largest multiple of **three** that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

**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: ""
```

**Example 4:**

```
Input: digits = [0,0,0,0,0,0]
Output: "0"
```

**Constraints:**

* `1 <= digits.length <= 10^4`
* `0 <= digits[i] <= 9`
* The returning answer must not contain unnecessary leading zeros.

给一个数，能去掉一部分数字并重新组合成为3的倍数，最大能组成的数可能是多少。这里要利用到一个性质，三的倍数满足每个位上的数字相加也是三的倍数，同时当余数不为0时，去掉会导致余数为1或2的数也就能生成3的倍数。分为两种情况，单个数导致的余数为1或2，和两个数相加除3导致的余数为1或2。不用考虑三个数的情况，因为（不考虑0）三个数和一定大于等于3，以被前面两种情况包括。因此在从大到小排序后满足数尽量大后，对以上Ⅴ种情况分类讨论。

```cpp
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        sort(digits.begin(), digits.end(), greater<int>());
        int sum = accumulate(digits.begin(), digits.end(), 0);
        if (sum == 0) return "0";
        const int N = digits.size();
        const auto print = [&]() {
            if (digits[0] == '0') return to_string(0);
            stringstream ss;
            for (const auto d : digits) {
                if (d == -1) continue;
                ss << d;
            }
            return ss.str();
        };
        if (sum % 3 == 0) return print();
        if (sum % 3 == 1) {
            for (int i = N - 1; i >= 0; --i) {
                if (digits[i] == 1 or digits[i] == 4 or digits[i] == 7) {
                    digits[i] = -1;
                    return print();
                }
            }
            for (int i = N - 1, cnt = 0; i >= 0; --i) {
                if (digits[i] == 2 or digits[i] == 5 or digits[i] == 8) {
                    digits[i] = -1;
                    if (cnt == 1) {
                        return print();
                    }
                    ++cnt;
                }
            }
        }
        if (sum % 3 == 2) {
            for (int i = N - 1; i >= 0; --i) {
                if (digits[i] == 2 or digits[i] == 5 or digits[i] == 8) {
                    digits[i] = -1;
                    return print();
                }
            }
            for (int i = N - 1, cnt = 0; i >= 0; --i) {
                if (digits[i] == 1 or digits[i] == 4 or digits[i] == 7) {
                    digits[i] = -1;
                    if (cnt == 1) {
                        return print();
                    }
                    ++cnt;
                }
            }
        }
        return "";
    }
};
```