หาตำแหน่งตัวเลขที่ต้องลบเพื่อให้หาร 6 ลงตัวใน C++

โจทย์

ให้ตัวเลข (เป็นสตริง) ต้องการลบตัวเลข 1 หลัก เพื่อให้ตัวเลขที่เหลือหาร 6 ลงตัว คืนตำแหน่ง (1-based index) ที่ต้องลบ

ตัวอย่าง: "1324" → ลบหลักที่ 4 (เลข 4) ได้ 132 หาร 6 ลงตัว → Output: 4

วิธีแก้ปัญหา

ตัวเลขหาร 6 ลงตัว ต้องหาร 2 และ 3 ลงตัว พิจารณากรณี:

หลักสุดท้ายเป็นคี่

ต้องลบหลักสุดท้ายเท่านั้น และหลักก่อนหน้าต้องเป็นคู่ และผลรวมตัวเลขลบหลักสุดท้ายหาร 3 ลงตัว

หลักสุดท้ายเป็นคู่

หา remainder เมื่อหาร 3:

• Remainder 1 → ลบหลักที่เป็น 1,4,7 (เลือกหลักที่ทำให้ตัวเลขที่เหลือมากที่สุด)
• Remainder 2 → ลบหลักที่เป็น 2,5,8
• Remainder 0 → ลบหลักที่เป็น 3,6,9

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

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

void isDivisibleBy6(string num) {
    int n = num.length();
    int a[n];
    int sum = 0;
    for (int i = 0; i < n; i++) { a[i] = num[i] - '0'; sum += a[i]; }
    if (a[n - 1] % 2) { // หลักสุดท้ายคี่
        if ((a[n - 2] % 2 != 0) || (sum - a[n - 1]) % 3 != 0) cout << "-1";
        else cout << n;
    } else { // หลักสุดท้ายคู่
        int re = sum % 3;
        int del = -1, flag = 0;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] % 3 == re) {
                if (a[i + 1] > a[i]) { del = i; flag = 1; break; }
                else del = i;
            }
        }
        if (flag == 0) {
            if (a[n - 2] % 2 == 0 && re == a[n - 1] % 3) del = n - 1;
        }
        if (del == -1) cout << -1;
        else cout << del + 1;
    }
}

int main() {
    string number = "343224152";
    isDivisibleBy6(number);
    return 0;
}

ผลลัพธ์

5