หาตัวเลขที่หาร 3 ลงตัวมากที่สุดจาก Digits Array (Set 2) ใน C++

โจทย์: กำหนด array of digits หาตัวเลขที่หาร 3 ลงตัวมากที่สุดโดยการต่อ digits บางส่วนในลำดับใดก็ได้ คำตอบอาจใหญ่มาก → return string ถ้าไม่มีคืน empty string

ตัวอย่าง: [7,2,8] → 87 (8+7=15 หาร 3 ลงตัว)

หลักการ: Divisibility by 3

ตัวเลขหาร 3 ลงตัว ↔ ผลรวม digits หาร 3 ลงตัว กลยุทธ์:

1. จัดกลุ่ม digits ตาม digit % 3 (0, 1, 2)
2. คำนวณ sum % 3
3. ถ้า sum % 3 != 0:
   • ลองลบ 1 digit จากกลุ่ม sum%3 (ค่าน้อยที่สุด)
   • ถ้าไม่มี → ลบ 2 digits จากกลุ่ม 3 - sum%3
4. รวม digits ที่เหลือ เรียง descending → ได้เลขมากที่สุด
5. Edge case: leading zeros → return "0"

ตัวอย่างโค้ด 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 x : digits) {
            d[x % 3].push_back(x);
            sum += x;
            sum %= 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,8};
    cout << ob.largestMultipleOfThree(v);
}

อินพุต

{7,2,8}

เอาต์พุท

87

Complexity

• Time: O(N log N) จาก sort
• Space: O(N)