Tìm bội số lớn nhất của 2, 3 và 5 từ mảng chữ số C++

Cho mảng arr[] kích thước N chỉ chứa chữ số 0-9. Nhiệm vụ: tìm số lớn nhất chia hết cho 2, 3 và 5 (tức chia hết cho 30).

Ví dụ minh họa

Input: arr[] = {1, 0, 5, 2} Output: 510

510 chia hết cho 2, 3, 5.

Phương pháp giải

Số chia hết cho 2 và 5 → phải có chữ số 0 ở cuối. Sắp xếp các chữ số còn lại giảm dần, đảm bảo tổng chữ số chia hết cho 3 (chia hết cho 30).

Ví dụ chương trình

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

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

int main(){
    Solution ob;
    vector<int> v = {7, 2, 0, 8};
    sort(v.begin(), v.end(), greater<int>());
    if (v.back() != 0) cout << "Không thể!";
    else cout << "Số lớn nhất: " << ob.largestMultipleOfThree(v);
    return 0;
}

Kết quả

Số lớn nhất: 870