In vị trí chữ số cần xóa để số chia hết 6 C++

Cho số dưới dạng chuỗi. Xóa 1 chữ số để số còn lại chia hết cho 6 (chia hết 2 và 3). Trả về vị trí (1-based) cần xóa, ưu tiên số kết quả lớn nhất. Ví dụ: "1324" → xóa vị trí 4 được "132" chia hết 6.

Phân tích theo chữ số cuối

• Chữ số cuối lẻ: chỉ có thể xóa chữ số cuối. Kiểm tra số mới chia hết 3 và chữ số mới cuối chẵn.
• Chữ số cuối chẵn: tính sum%3. Cần xóa chữ số có digit%3 == sum%3. Ưu tiên xóa chữ số nhỏ hơn chữ số sau nó để số kết quả lớn nhất.

Ví dụ minh họa

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

void findRemovalPos(string num) {
    int n = num.size();
    vector 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 == 1) {  // cuoi le
        if (a[n-2] % 2 == 0 && (sum - a[n-1]) % 3 == 0)
            cout << n;
        else
            cout << -1;
    } else {  // cuoi chan
        int rem = sum % 3;
        int del = -1;
        for (int i = 0; i < n-1; i++) {
            if (a[i] % 3 == rem) {
                if (i+1 < n && a[i+1] > a[i]) { del = i; break; }
                del = i;
            }
        }
        if (del == -1 && a[n-2] % 2 == 0 && a[n-1] % 3 == rem)
            del = n-1;
        cout << (del == -1 ? -1 : del+1);
    }
}

int main() {
    string num = "343224152";
    findRemovalPos(num);  // 5
    return 0;
}

Kết quả

5