Số lớn nhất chia hết cho 3 từ mảng chữ số (Phiên bản 2) trong C++

Cho mảng chữ số (0-9). Tìm số lớn nhất (dạng chuỗi) chia hết cho 3 bằng cách nối một số chữ số theo thứ tự bất kỳ. Trả về chuỗi rỗng nếu không có.

Ví dụ

Input: [7,2,8] → Output: "87" (87 chia hết cho 3, lớn nhất).

Thuật toán

• Sắp xếp chữ số giảm dần.
• Phân loại theo modulo 3: nhóm 0, 1, 2.
• Tính tổng modulo 3.
  • Nếu dư 0: dùng tất cả.
  • Nếu dư 1: bỏ 1 số nhóm 1 (nhỏ nhất) HOẶC 2 số nhóm 2.
  • Nếu dư 2: bỏ 1 số nhóm 2 HOẶC 2 số nhóm 1.
• Ghép các số còn lại (đã sắp giảm dần) → kết quả.
• Xử lý trường hợp toàn số 0 → trả về "0".

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

string largestMultipleOfThree(vector<int>& digits) {
    vector<vector<int>> mod(3);
    sort(digits.begin(), digits.end(), greater<int>());
    int sum = 0;
    for (int d : digits) {
        mod[d % 3].push_back(d);
        sum = (sum + d) % 3;
    }
    
    if (sum == 1) {
        if (!mod[1].empty()) mod[1].pop_back();
        else if (mod[2].size() >= 2) { mod[2].pop_back(); mod[2].pop_back(); }
        else return "";
    } else if (sum == 2) {
        if (!mod[2].empty()) mod[2].pop_back();
        else if (mod[1].size() >= 2) { mod[1].pop_back(); mod[1].pop_back(); }
        else return "";
    }
    
    string res;
    for (int i = 0; i < 3; i++)
        for (int d : mod[i]) res += to_string(d);
    
    sort(res.begin(), res.end(), greater<char>());
    if (!res.empty() && res[0] == '0') return "0";
    return res;
}

int main() {
    vector<int> v = {7,2,8};
    cout << largestMultipleOfThree(v); // 87
    return 0;
}

Kết quả

87

Độ phức tạp: O(n log n) do sắp xếp.