Các cách cắt số sao cho phần lớn nhất chia hết cho 3 trong C++

Trong bài toán này, cho một số nguyên lớn (lên đến 10⁵ chữ số). Nhiệm vụ in tổng số lần cắt cần thiết sao cho số lượng phần chia hết cho 3 là nhiều nhất.

Ví dụ minh họa:

Đầu vào - 9216

Kết quả - 3

Giải thích - Số được chia thành 9|21|6.

Để giải bài toán, bắt đầu từ chữ số ít quan trọng nhất (chữ số cuối). Tìm số nhỏ nhất chia hết cho 3. Cập nhật đếm dựa trên đó.

Ví dụ - Nếu arr[i] tạo số chia hết 3, tăng đếm và chuyển sang chữ số tiếp. Nếu không chia hết, kết hợp với chữ số tiếp theo và kiểm tra chia hết cho 3.

Quy tắc chia hết cho 3 - Một số chia hết cho 3 nếu tổng các chữ số của nó chia hết cho 3.

Chương trình minh họa

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

int countMaximum3DivisibleNumbers(string number) { 
    int n = number.length(); 
    vector<int> remIndex(3, -1); 
    remIndex[0] = 0; 
    vector<int> counter(n + 1); 
    int r = 0; 
    for (int i = 1; i <= n; i++) { 
        r = (r + number[i-1] - '0') % 3; 
        counter[i] = counter[i-1]; 
        if (remIndex[r] != -1) 
            counter[i] = max(counter[i], counter[remIndex[r]] + 1); 
        remIndex[r] = i+1; 
    } 
    return counter[n]; 
} 

int main() { 
    string number = "216873491"; 
    cout << "Số lượng phần chia hết cho 3 từ cắt số " << number << " là: " << countMaximum3DivisibleNumbers(number); 
    return 0; 
}

Kết quả

Số lượng phần chia hết cho 3 từ cắt số 216873491 là: 5