可能的数字削减，以便在C ++中最大部分可以被3整除

在这个问题中，我们得到一个大的整数值（最多10 ^5个数字）。我们的任务是打印所需切割的总数，以使最大部分被3整除。

让我们以一个例子来了解问题

输入-9216

输出-3

说明-数字除以9 | 21 | 6。

为了解决这个问题，我们必须从数字的最低有效位开始，即数字的最后一位。为此，我们将找到最小的三分之一。然后根据它更新计数。

示例-如果arr [i]将3整除，那么我们将增加计数并移至该数字的下一位。如果arr [i]不能被3整除，那么我们将其与下一位数字合并，并检查3的除数。

3的可除性-如果数字的位数可被3整除，则数字可被3整除。

示例

显示我们解决方案实施情况的程序

#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;
}

输出结果

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