# 1363.largest-multiple-of-three

## Statement

• Difficulty: Hard
• Tag: `贪心` `数组` `动态规划`

``````输入：digits = [8,1,9]

``````

``````输入：digits = [8,6,7,1,0]

``````

``````输入：digits = [1]

``````

``````输入：digits = [0,0,0,0,0,0]

``````

• `1 <= digits.length <= 10^4`
• `0 <= digits[i] <= 9`
• 返回的结果不应包含不必要的前导零。

• Link: Largest Multiple of Three
• Difficulty: Hard
• Tag: `Greedy` `Array` `Dynamic Programming`

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`

## Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
string largestMultipleOfThree(vector<int> &digits) {
auto f = vector<vector<int>>(3, vector<int>());
for (auto &d : digits) {
f[d % 3].push_back(d);
}

for (int i = 0; i < 3; i++) {
sort(all(f[i]), greater<int>());
}

{
int x = f[1].size();
int y = f[2].size();
int tot = (x + y * 2) % 3;

if (tot == 1) {
if (x) {
f[1].pop_back();

} else {
f[2].pop_back();
f[2].pop_back();
}
}

if (tot == 2) {
if (y) {
f[2].pop_back();
} else {
f[1].pop_back();
f[1].pop_back();
}
}
}

auto ff = vector<int>();
for (int i = 0; i < 3; i++) {
ff.insert(ff.begin(), all(f[i]));
}

sort(all(ff), greater<int>());

string res = "";

for (auto &a : ff) {
res += to_string(a);
}

if (res == "") {
return res;
}

int zero = 0;
for (auto &c : res) {
if (c == '0') {
++zero;
} else {
break;
}
}

if (zero == res.size()) {
return res.substr(zero - 1);
}

return res.substr(zero);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````