หาตัวเลขมากที่สุดที่หารด้วย 2, 3, 5 ลงตัวจาก Array หลักเดียวใน C++

ในปัญหานี้ เราได้รับ array ของหลักเลข (0-9) งานคือจัดเรียงให้ได้ตัวเลขมากที่สุดที่หารด้วย 2, 3, และ 5 ลงตัว (คือหาร 30 ลงตัว)

ตัวอย่าง

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

510 หาร 2, 3, 5 ลงตัวทั้งคู่

เงื่อนไขความเป็นไปได้

• ต้องมีเลข 0 อย่างน้อย 1 ตัว (เพื่อหาร 10 ลงตัว → หาร 2 และ 5 ลงตัว)
• ผลรวมหลักต้องหาร 3 ลงตัว (เพื่อหาร 3 ลงตัว)

วิธีการแก้ปัญหา: ใช้โค้ด Largest Multiple of Three + เช็คเลข 0

1. เช็คว่ามี 0 ใน array หรือไม่
2. ใช้ greedy algorithm หา largest multiple of three จากหลักที่เหลือ
3. ต่อ 0 ไปท้ายสุด

ตัวอย่างโค้ด

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

string largestMultipleOfThree(vector& digits) {
    vector> 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());
    if (!ret.empty() && ret[0] == '0') return "0";
    return ret;
}

int main() {
    vector v = {7, 2, 0, 8};
    sort(v.begin(), v.end(), greater());
    if (v.back() != 0) cout << "Not Possible!";
    else cout << "Largest number: " << largestMultipleOfThree(v);
    return 0;
}

ผลลัพธ์

The largest number is 870