C++で最大部分が3で割り切れるような数の可能なカット

この問題では、大きな整数値（最大10 ⁵ ）が与えられます。 数字）。私たちのタスクは、最大パーツが3で割り切れるように必要なカットの総数を印刷することです。

問題を理解するために例を見てみましょう

入力 − 9216

出力 − 3

説明 −数値は9 | 21|6として除算されます。

この問題を解決するには、数値の最下位ビット、つまり数値の最後の桁から開始する必要があります。ここでは、3で割り切れる最小の数を見つけます。そして、それに基づいてカウントを更新します。

例 − 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