Bội số lớn nhất của 3 trong C++

Cho một mảng các chữ số, ta cần tìm bội số lớn nhất của 3 có thể tạo được bằng cách nối một số chữ số cho trước theo bất kỳ thứ tự nào. Kết quả có thể rất lớn nên trả về dưới dạng chuỗi. Nếu không có đáp án, trả về chuỗi rỗng.

Ví dụ, nếu đầu vào là [7,2,8], đầu ra sẽ là 87.

Giải pháp

Các bước thực hiện:

• Tạo mảng 2D d với 3 hàng (cho các dư 0, 1, 2 khi chia cho 3)
• Sắp xếp mảng digits giảm dần
• Tính tổng các chữ số và lấy dư cho 3
• Phân loại từng chữ số vào d[x % 3]
• Nếu tổng % 3 != 0: cần loại bỏ chữ số để tổng chia hết cho 3
  • Nếu d[sum] không rỗng: loại bỏ phần tử cuối (nhỏ nhất) của d[sum]
  • Ngược lại: loại bỏ 2 phần tử cuối của d[3-sum]
• Ghép các chữ số còn lại theo thứ tự giảm dần
• Nếu kết quả bắt đầu bằng '0', trả về "0"

Ví dụ mã C++

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

class Solution { 
public: 
    string largestMultipleOfThree(vector<int>& digits) { 
        vector<vector<int>> d(3); 
        sort(digits.begin(), digits.end(), greater<int>()); 
        int sum = 0; 
        
        for (int i = 0; i < digits.size(); i++) { 
            int x = digits[i]; 
            d[x % 3].push_back(digits[i]); 
            sum += x; 
            sum %= 3; 
        } 
        
        if (sum) { 
            if (!d[sum].size()) { 
                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 j = 0; j < d[i].size(); j++) { 
                ret += to_string(d[i][j]); 
            } 
        } 
        
        sort(ret.begin(), ret.end(), greater<int>()); 
        if (ret.size() && ret[0] == '0') return "0"; 
        return ret; 
    } 
}; 

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

Đầu vào

{7,2,8}

Đầu ra

87