Có thể cắt một số sao cho các phần lớn nhất chia hết cho 3 trong C ++

Trong bài toán này, chúng ta được cung cấp một giá trị số nguyên lớn (với tối đa 10 ⁵ chữ số). Nhiệm vụ của chúng tôi là in ra tổng số vết cắt được yêu cầu sao cho các phần lớn nhất chia hết cho 3.

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào - 9216

Đầu ra - 3

Giải thích - số bị chia là 9 | 21 | 6.

Để giải quyết vấn đề này, chúng ta sẽ phải bắt đầu cho bit có ý nghĩa nhỏ nhất của số, tức là chữ số cuối cùng của số. Đối với đây, chúng ta sẽ tìm số nhỏ nhất chia hết cho ba. Và sau đó cập nhật số lượng dựa trên nó.

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

Tính chia hết của 3 - Một số chia hết cho 3 nếu số chữ số của số đó chia hết cho ba.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi

#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<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
   return 0;
}

Đầu ra

The number of 3 divisible number created by cutting 216873491 are : 5