C++の整数の文字列で6で割り切れる部分文字列の数

整数文字列が与えられ、整数形式で6で割り切れる部分文字列の数を決定する必要がある問題を見ていきます。入力は、数値（整数）で構成される文字列の形式であることに注意してください。それでも、分割可能性チェックは整数のみと見なして実行されます（文字列入力のASC​​II値は使用されません）。

入力

str = “648”

出力

説明

サブストリング「6」、「48」、および「648」は6で割り切れる。

入力

str = “38342”

出力

4

説明

サブストリング「3834」、「342」、「834」、および「42」は6で割り切れる。

ブルートフォースアプローチ

ユーザーは、考えられるすべての部分文字列をチェックして、6で割り切れるかどうかを確認できます。部分文字列が割り切れる場合は、さらにカウントします。この方法では、問題の解決に時間がかかり、タスクの完了にO（n2）時間がかかります。

例

#include <bits/stdc++.h>
using namespace std;
int
str_to_int (string str, int i, int j) {
   int temp = 0;
   for (; i <= j; i++) {
      temp = temp * 10 + (str[i] - '0');
   }
   return temp;
}
int main () {
   char str[] = "24661";
   int n = strlen (str);
   int count = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
         int temp = str_to_int (str, i, j);
         if (temp % 6 == 0) count++;
      }
   }
   cout << count << endl;
   return 0;
}

出力

6

効率的なアプローチ

数値の最後の桁は、6で割り切れるには、2で割り切れる必要があります。合計桁数は3である必要があります。以前に計算された回答を追跡することにより、動的計画法を利用して解決策を見つけることができます。

f（i、s）-3を法とする桁の合計がsであるi番目のインデックスからの文字列の数とします。これによりΣin-1f（i、0）が得られます。

aを文字列のi番目の桁とします。ここで、f（i、s）から、偶数でi + 1で始まるすべての部分文字列を見つける必要があります。（a + s）が3で割り切れる場合、追加の部分文字列を生成できます。したがって、漸化式が形成されます。 、

f（i、s）=f（i + 1、（s + a）％3）+（a％2 ==0 AND（a + s）％3 ==0）。

例2

#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]){
   // when reached end of string.
   if (i == strlen(str))
      return 0;
   // if already computed then return result.
   if (dp[i][s] != -1)
      return dp[i][s];
   int a = str[i] - '0';
   int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp);
   return dp[i][s] = ans;
}
int main(){
   char str[] = "24661";
   int n = strlen(str);
   // dp array to store all states.
   int dp[n+1][3];
   memset(dp, -1, sizeof dp);
   int count = 0;
   for (int i = 0; i < n; i++){
      // if any position contains 0 increment count.
      if (str[i] == '0')
         count++;
      // Passing previous sum modulo 3 = 0 to recursive function.
      else
         count += find(i, 0, str, dp);
   }
   cout << "Number of substrings divisible by 6: " << count << endl;
   return 0;
}

出力

Number of substrings divisible by 6: 6

時間計算量：O（N）

結論

このチュートリアルでは、動的計画法を使用して、整数の文字列で6で割り切れる部分文字列の数を検出する方法を学習しました。同じプログラムは、C、Java、Pythonなどの異なる言語で記述されている場合があります。このレッスンがお役に立てば幸いです。