Số lớn nhất từ N chữ số chia hết 2,3,5 C++

Cho mảng chữ số. Tạo số lớn nhất (sắp xếp giảm dần) chia hết cho 2, 3, 5.

Điều kiện chia hết cho 2,3,5 ⇔ chia hết cho 30 ⇔ kết thúc bằng 0 VÀ tổng chữ số chia hết cho 3.

Thuật toán

• Phải có chữ số 0. Nếu không → "Not possible".
• Sắp xếp giảm dần.
• Tính tổng chữ số, tìm dư sum % 3.
• Nếu dư ≠ 0: xóa chữ số nhỏ nhất có dư tương ứng (hoặc 2 chữ số dư = 3-dư).
• Kết quả: các chữ số còn lại (đã sắp xếp giảm) + 0 ở cuối.

Triển khai C++

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

string largestDivisible235(vector& digits) {
    bool hasZero = false;
    int sum = 0;
    for (int d : digits) { if (d == 0) hasZero = true; sum += d; }
    if (!hasZero) return "Not possible";

    sort(digits.rbegin(), digits.rend()); // giảm dần

    int rem = sum % 3;
    if (rem != 0) {
        // thử xóa 1 chữ số dư = rem
        bool removed = false;
        for (int i = digits.size()-1; i >= 0; i--) {
            if (digits[i] % 3 == rem) { digits.erase(digits.begin()+i); removed = true; break; }
        }
        if (!removed) {
            // xóa 2 chữ số dư = 3-rem
            int need = 3 - rem, cnt = 0;
            for (int i = digits.size()-1; i >= 0 && cnt < 2; i--) {
                if (digits[i] % 3 == need) { digits.erase(digits.begin()+i); cnt++; i++; }
            }
        }
    }
    if (digits.empty() || digits[0] == 0) return "0";
    string res;
    for (int d : digits) res += char('0' + d);
    return res;
}

int main() {
    vector v = {4,5,0,3,2,4,5,6,7};
    cout << largestDivisible235(v) << endl; // 765544320
    return 0;
}

Kết quả

765544320