Dada una string de dígitos “0-9”. La tarea es encontrar el número de substrings que son divisibles por 8 pero no por 3.
Ejemplos:
Input : str = "888"
Output : 5
Substring indexes : (1, 1), (1, 2), (2, 2),
(2, 3), (3, 3).
Input : str = "6564525600"
Output : 15
Un número es divisible por 3 si la suma de sus dígitos es divisible por 3. Y el número es divisible por 8 si los últimos tres dígitos son divisibles por 8. Ahora, la idea es almacenar la suma de prefijos de la string, es decir, el recuento de prefijos tales esa suma de los dígitos del prefijo módulo 3 es 0, 1, 2.
Luego iteramos sobre la string y para cada posición i, contamos el número de substrings que terminan en i y son divisibles por 8. De este valor, restamos el número de substrings que terminan en i y son divisibles por 3. Definimos una |S| Array 2D de tamaño X 3, |S| es el tamaño de la string, digamos dp[i][j]. dp[i][j] se puede definir como en cualquier índice i, número de substring que comienza desde el índice 0 hasta el índice i que tiene una salida j cuando los dígitos del índice 0 se suman al índice i y al módulo 3. Por lo tanto, 0 <= j <= 2, desde el módulo 3.
Ahora, iteraremos sobre la string y verificaremos cada número de un dígito, número de dos dígitos y número de tres dígitos que son divisibles por 8. Para un dígito, solo verifique si el carácter en el índice es 8 o no. Para dos dígitos, comprueba si es divisible por 8 y no por 3. Para tres dígitos, forma el número y comprueba si es divisible por 8 o no. Si el número es divisible, los últimos tres dígitos deben ser divisibles por 8.
Entonces, todas las substrings que terminan en este índice deben ser divisibles por 8, es decir, (i-3) substrings. Pero también contendrá esas substrings que son divisibles por 3, así que simplemente elimínelas usando dp[i][j].
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP Program to count substrings which are
// divisible by 8 but not by 3
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// Returns count of substrings divisible by 8
// but not by 3.
int count(char s[], int len)
{
int cur = 0, dig = 0;
int sum[MAX], dp[MAX][3];
memset(sum, 0, sizeof(sum));
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
// Iterating the string.
for (int i = 1; i <= len; i++)
{
dig = int(s[i-1])-48;
cur += dig;
cur %= 3;
sum[i] = cur;
// Prefix sum of number of substrings whose
// sum of digits modulo 3 is 0, 1, 2.
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-1][2];
dp[i][sum[i]]++;
}
int ans = 0, dprev = 0, value = 0, dprev2 = 0;
// Iterating the string.
for (int i = 1; i <= len; i++)
{
dig = int(s[i-1])-48;
// Since single digit 8 is divisible
// by 8 and not by 3.
if (dig == 8)
ans++;
// Taking two digit number.
if (i-2 >= 0)
{
dprev = int(s[i-2])-48; // 10th position
value = dprev*10 + dig; // Complete 2 digit
// number
if ((value%8 == 0) && (value%3 != 0))
ans++;
}
// Taking 3 digit number.
if (i-3 >= 0)
{
dprev2 = int(s[i-3])-48; // 100th position
dprev = int(s[i-2])-48; // 10th position
// Complete 3 digit number.
value = dprev2*100 + dprev*10 + dig;
if (value%8 != 0)
continue;
// If number formed is divisible by 8 then
// last 3 digits are also divisible by 8.
// Then all the substring ending at this
// index is divisible.
ans += (i-2);
// But those substring also contain number
// which are not divisible by 3 so
// remove them.
ans -= (dp[i-3][sum[i]]);
}
}
return ans;
}
// Driven Program
int main()
{
char str[] = "6564525600";
int len = strlen(str);
cout << count(str, len) <<endl;
return 0;
}
Java
// Java program to count substrings which are
// divisible by 8 but not by 3
import java.io.*;
class GFG
{
// Function that returns count of substrings divisible by 8
// but not by 3
static int count(String s, int len)
{
int MAX = 1000;
int cur = 0, dig = 0;
int[] sum = new int[MAX];
int[][] dp = new int[MAX][3];
dp[0][0] = 1;
// Iterating the string.
for (int i = 1; i <= len; i++)
{
dig = (int)(s.charAt(i-1)) - 48;
cur += dig;
cur %= 3;
sum[i] = cur;
// Prefix sum of number of substrings whose
// sum of digits modulo 3 is 0, 1, 2.
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-1][2];
dp[i][sum[i]]++;
}
int ans = 0, dprev = 0, value = 0, dprev2 = 0;
// Iterating the string.
for (int i = 1; i <= len; i++)
{
dig = (int)(s.charAt(i-1)) - 48;
// Since single digit 8 is divisible
// by 8 and not by 3.
if (dig == 8)
ans++;
// Taking two digit number.
if (i-2 >= 0)
{
dprev = (int)(s.charAt(i-2)) - 48; // 10th position
value = dprev*10 + dig; // Complete 2 digit
// number
if ((value%8 == 0) && (value%3 != 0))
ans++;
}
// Taking 3 digit number.
if (i-3 >= 0)
{
dprev2 = (int)(s.charAt(i-3)) - 48; // 100th position
dprev = (int)(s.charAt(i-2)) - 48; // 10th position
// Complete 3 digit number.
value = dprev2*100 + dprev*10 + dig;
if (value%8 != 0)
continue;
// If number formed is divisible by 8 then
// last 3 digits are also divisible by 8.
// Then all the substring ending at this
// index is divisible.
ans += (i-2);
// But those substring also contain number
// which are not divisible by 3 so
// remove them.
ans -= (dp[i-3][sum[i]]);
}
}
return ans;
}
// driver program
public static void main (String[] args)
{
String str = "6564525600";
int len = str.length();
System.out.println(count(str, len));
}
}
// Contributed by Pramod Kumar
Python3
# Python3 Program to count substrings # which are divisible by 8 but not by 3 # Returns count of substrings # divisible by 8 but not by 3. def count(s, Len): global MAX cur = 0 dig = 0 Sum = [0] * MAX dp = [[0, 0, 0] for i in range(MAX)] dp[0][0] = 1 # Iterating the string. for i in range(1, Len + 1): dig = int(s[i - 1]) - 48 cur += dig cur %= 3 Sum[i] = cur # Prefix sum of number of substrings # whose sum of digits modulo 3 is # 0, 1, 2. dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] dp[i][2] = dp[i - 1][2] dp[i][Sum[i]] += 1 ans = 0 dprev = 0 value = 0 dprev2 = 0 # Iterating the string. for i in range(1, Len + 1): dig = int(s[i - 1]) - 48 # Since single digit 8 is # divisible by 8 and not by 3. if dig == 8: ans += 1 # Taking two digit number. if i - 2 >= 0: dprev = int(s[i - 2]) - 48 # 10th position value = dprev * 10 + dig # Complete 2 digit # number if (value % 8 == 0) and (value % 3 != 0): ans += 1 # Taking 3 digit number. if i - 3 >= 0: dprev2 = int(s[i - 3]) - 48 # 100th position dprev = int(s[i - 2]) - 48 # 10th position # Complete 3 digit number. value = (dprev2 * 100 + dprev * 10 + dig) if value % 8 != 0: continue # If number formed is divisible by 8 # then last 3 digits are also divisible # by 8. Then all the substring ending # at this index are divisible. ans += (i - 2) # But those substring also contain # number which are not divisible # by 3 so remove them. ans -= (dp[i - 3][Sum[i]]) return ans # Driver Code MAX = 1000 Str = "6564525600" Len = len(Str) print(count(Str, Len)) # This code is contributed # by PranchalK
C#
// C# program to count substrings which are
// divisible by 8 but not by 3
using System;
class GFG
{
// Function that returns count of substrings
// divisible by 8 but not by 3
static int count(String s, int len)
{
int MAX = 1000;
int cur = 0, dig = 0;
int[] sum = new int[MAX];
int[,] dp = new int[MAX,3];
dp[0, 0] = 1;
// Iterating the string.
for (int i = 1; i <= len; i++)
{
dig = (int)(s[i-1]) - 48;
cur += dig;
cur %= 3;
sum[i] = cur;
// Prefix sum of number of substrings whose
// sum of digits modulo 3 is 0, 1, 2.
dp[i, 0] = dp[i-1, 0];
dp[i, 1] = dp[i-1, 1];
dp[i, 2] = dp[i-1, 2];
dp[i, sum[i]]++;
}
int ans = 0, dprev = 0, value = 0, dprev2 = 0;
// Iterating the string.
for (int i = 1; i <= len; i++)
{
dig = (int)(s[i-1]) - 48;
// Since single digit 8 is divisible
// by 8 and not by 3.
if (dig == 8)
ans++;
// Taking two digit number.
if (i-2 >= 0)
{
dprev = (int)(s[i-2]) - 48; // 10th position
value = dprev*10 + dig; // Complete 2 digit number
if ((value % 8 == 0) && (value % 3 != 0))
ans++;
}
// Taking 3 digit number.
if (i - 3 >= 0)
{
dprev2 = (int)(s[i-3]) - 48; // 100th position
dprev = (int)(s[i-2]) - 48; // 10th position
// Complete 3 digit number.
value = dprev2 * 100 + dprev * 10 + dig;
if (value % 8 != 0)
continue;
// If number formed is divisible by 8 then
// last 3 digits are also divisible by 8.
// Then all the substring ending at this
// index is divisible.
ans += (i - 2);
// But those substring also contain number
// which are not divisible by 3 so
// remove them.
ans -= (dp[i - 3,sum[i]]);
}
}
return ans;
}
// driver program
public static void Main (String[] args)
{
String str = "6564525600";
int len = str.Length;
Console.Write(count(str, len));
}
}
// This code is contributed by parashar.
Javascript
<script>
// JavaScript Program to count substrings
// which are divisible by 8 but not by 3
// Returns count of substrings
// divisible by 8 but not by 3.
let MAX = 1000
function count(s, Len){
let cur = 0
let dig = 0
let Sum = new Array(MAX).fill(0)
let dp = new Array(MAX);
for(let i=0;i<MAX;i++){
dp[i] = [0, 0, 0]
}
dp[0][0] = 1
// Iterating the string.
for(let i=1;i<Len + 1;i++){
dig = s.charCodeAt(i - 1) - '0'.charCodeAt(0)
cur += dig
cur %= 3
Sum[i] = cur
// Prefix sum of number of substrings
// whose sum of digits modulo 3 is
// 0, 1, 2.
dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 1][2]
dp[i][Sum[i]] += 1
}
let ans = 0
let dprev = 0
let value = 0
let dprev2 = 0
// Iterating the string.
for(let i=1;i<Len + 1;i++){
dig = s.charCodeAt(i - 1) - '0'.charCodeAt(0)
// Since single digit 8 is
// divisible by 8 and not by 3.
if(dig == 8)
ans += 1
// Taking two digit number.
if(i - 2 >= 0){
dprev = s.charCodeAt(i - 2) - '0'.charCodeAt(0) // 10th position
value = dprev * 10 + dig // Complete 2 digit
// number
if ((value % 8 == 0) && (value % 3 != 0))
ans += 1
}
// Taking 3 digit number.
if(i - 3 >= 0){
dprev2 = s.charCodeAt(i - 3) - '0'.charCodeAt(0) // 100th position
dprev = s.charCodeAt(i - 2) - '0'.charCodeAt(0) // 10th position
// Complete 3 digit number.
value = (dprev2 * 100 +
dprev * 10 + dig)
if(value % 8 != 0)
continue
// If number formed is divisible by 8
// then last 3 digits are also divisible
// by 8. Then all the substring ending
// at this index are divisible.
ans += (i - 2)
// But those substring also contain
// number which are not divisible
// by 3 so remove them.
ans -= (dp[i - 3][Sum[i]])
}
}
return ans
}
// Driver Code
let Str = "6564525600"
let Len = Str.length
document.write(count(Str, Len))
// This code is contributed by shinjanpatra
</script>
15
Complejidad de tiempo: O (len), donde len es la longitud de la string.
Espacio Auxiliar: O(MAX), Donde MAX es la constante definida.
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Por favor
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA