Số chữ số cần xóa để số chia hết cho 3 trong C++

Cho một số dưới dạng chuỗi. Cần tìm số chữ số tối thiểu phải xóa để số còn lại chia hết cho 3. Theo tính chất chia hết cho 3, ta chỉ cần xóa tối đa 2 chữ số.

Ví dụ

Đầu vào: 92 → Đầu ra: 1 (xóa 2 → 9 chia hết cho 3)

Đầu vào: 999 → Đầu ra: 0 (đã chia hết cho 3)

Thuật toán

• Tính tổng các chữ số.
• Nếu tổng chia hết cho 3 → trả về 0.
• Nếu độ dài = 1 và không chia hết → trả về -1.
• Duyệt từng chữ số: nếu xóa chữ số đó làm tổng chia hết cho 3 → trả về 1.
• Nếu độ dài = 2 → trả về -1.
• Ngược lại trả về 2 (luôn có thể xóa 2 chữ số để chia hết).

Triển khai C++

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

int getNumSum(string n) {
    int sum = 0;
    for (char c : n) sum += c - '0';
    return sum;
}

int getDigitsCount(string num) {
    int n = num.length();
    int sum = getNumSum(num);
    if (sum % 3 == 0) return 0;
    if (n == 1) return -1;
    for (int i = 0; i < n; i++) {
        int digit = num[i] - '0';
        if ((sum - digit) % 3 == 0) return 1;
    }
    if (n == 2) return -1;
    return 2;
}

int main() {
    string num = "7536836";
    cout << getDigitsCount(num) << endl; // Output: 1
    return 0;
}

Kết quả

1