Número de substrings divisibles por 6 en una string de enteros

Dada una string que consta de números enteros del 0 al 9. La tarea es contar el número de substrings que, cuando se convierten en enteros, son divisibles por 6. La substring no contiene ceros a la izquierda. Ejemplos:

Input : s = "606".
Output : 5
Substrings "6", "0", "6", "60", "606"
are divisible by 6.

Input : s = "4806".
Output : 5
"0", "6", "48", "480", "4806" are 
substring which are divisible by 6.

Método 1: (Fuerza bruta) La idea es encontrar todas las substrings de la string dada y verificar si la substring es divisible por 6 o no

Complejidad Temporal: O(n 2 ).

 Método 2: (Programación dinámica) Como se discutió en Comprobar si un número grande es divisible por 6 o no . Un número es divisible por 6 si el último dígito es divisible por 2 y la suma de los dígitos es divisible por 3. La idea es usar la programación dinámica, que nos permite calcular la respuesta de manera rápida y eficiente al rastrear las respuestas calculadas previamente y usar estas respuestas almacenadas en su lugar. de recalcular valores. 

Sea f(i, m) el número de strings que comienzan en el índice i y la suma de sus dígitos módulo 3 (hasta ahora) es my el número que representa es par . Entonces, nuestra respuesta sería {\displaystyle \sum_{i}^{n-1}f(i,0) }

Sea x el i -ésimo dígito de la string. De f(i, m) necesitamos encontrar todas las substrings pares que comienzan en i + 1. Además, obtendremos una substring extra si (x + m) es divisible por 3 y x es par. Entonces, obtenemos la relación de recurrencia

// We initially pass m (sum modulo 3 so far) as 0
f(i, m) = ((x + m)%3 == 0 and x%2 == 0) + 
          f(i + 1, (m + x)%3)  // Recursive 

Al memorizar los estados, obtenemos la solución O(n). A continuación se muestra la implementación de este enfoque: 

C++

// C++ program to calculate number of substring
// divisible by 6.
#include <bits/stdc++.h>
#define MAX 100002
using namespace std;
 
// Return the number of substring divisible by 6
// and starting at index i in s[] and previous sum
// of digits modulo 3 is m.
int f(int i, int m, char s[], int memoize[][3])
{
    // End of the string.
    if (i == strlen(s))
        return 0;
 
    // If already calculated, return the
    // stored value.
    if (memoize[i][m] != -1)
        return memoize[i][m];
 
    // Converting into integer.
    int x = s[i] - '0';
 
    // Increment result by 1, if current digit
    // is divisible by 2 and sum of digits is
    // divisible by 3.
    // And recur for next index with new modulo.
    int ans = ((x+m)%3 == 0 && x%2 == 0) +
              f(i+1, (m+x)%3, s, memoize);
 
    return memoize[i][m] = ans;
}
 
// Returns substrings divisible by 6.
int countDivBy6(char s[])
{
    int n = strlen(s);
 
    // For storing the value of all states.
    int memoize[n+1][3];
    memset(memoize, -1, sizeof memoize);
 
    int ans = 0;
    for (int i = 0; i < strlen(s); i++)
    {
        // If string contain 0, increment count by 1.
        if (s[i] == '0')
            ans++;
 
        // Else calculate using recursive function.
        // Pass previous sum modulo 3 as 0.
        else
            ans += f(i, 0, s, memoize);
    }
 
    return ans;
}
 
// Driven Program
int main()
{
    char s[] = "4806";
 
    cout << countDivBy6(s) << endl;
 
    return 0;
}

Java

// Java program to calculate number of substring
// divisible by 6.
import java.util.*;
 
class GFG
{
 
    static int MAX = 100002;
 
    // Return the number of substring divisible by 6
    // and starting at index i in s[] and previous sum
    // of digits modulo 3 is m.
    static int f(int i, int m, char s[], int memoize[][])
    {
        // End of the string.
        if (i == s.length)
        {
            return 0;
        }
 
        // If already calculated, return the
        // stored value.
        if (memoize[i][m] != -1)
        {
            return memoize[i][m];
        }
 
        // Converting into integer.
        int x = s[i] - '0';
 
        // Increment result by 1, if current digit
        // is divisible by 2 and sum of digits is
        // divisible by 3.
        // And recur for next index with new modulo.
        int ans = ((x + m) % 3 == 0 && x % 2 == 0) ? 1 + f(i + 1,
                (m + x) % 3, s, memoize) : f(i + 1, (m + x) % 3, s, memoize);
        memoize[i][m] = ans;
        return memoize[i][m];
    }
 
    // Returns substrings divisible by 6.
    static int countDivBy6(char s[])
    {
        int n = s.length;
 
        // For storing the value of all states.
        int[][] memoize = new int[n + 1][3];
        for (int i = 0; i < n + 1; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                memoize[i][j] = -1;
            }
        }
 
        int ans = 0;
        for (int i = 0; i < s.length; i++)
        {
            // If string contain 0, increment count by 1.
            if (s[i] == '0')
            {
                ans++;
            }
            // Else calculate using recursive function.
            // Pass previous sum modulo 3 as 0.
            else
            {
                ans += f(i, 0, s, memoize);
            }
        }
 
        return ans;
    }
 
    // Driven Program
    public static void main(String[] args)
    {
        char s[] = "4806".toCharArray();
 
        System.out.println(countDivBy6(s));
    }
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to calculate number
# of substring
 
# Return the number of substring divisible
# by 6 and starting at index i in s[] and
# previous sum of digits modulo 3 is m.
def f(i, m, s, memoize):
     
    # End of the string.
    if (i == len(s)):
        return 0
 
    # If already calculated, return
    # the stored value.
    if (memoize[i][m] != -1):
        return memoize[i][m]
 
    # Converting into integer.
    x = ord(s[i]) - ord('0')
 
    # Increment result by 1, if current digit
    # is divisible by 2 and sum of digits is
    # divisible by 3.
    # And recur for next index with new modulo.
    ans = (((x + m) % 3 == 0 and x % 2 == 0) +
          f(i + 1, (m + x) % 3, s, memoize))
 
    memoize[i][m] = ans
    return memoize[i][m]
 
# Returns substrings divisible by 6.
def countDivBy6(s):
    n = len(s)
 
    # For storing the value of all states.
    memoize = [[-1] * 3 for i in range(n + 1)]
 
    ans = 0
    for i in range(len(s)):
         
        # If string contain 0, increment
        # count by 1.
        if (s[i] == '0'):
            ans += 1
 
        # Else calculate using recursive function.
        # Pass previous sum modulo 3 as 0.
        else:
            ans += f(i, 0, s, memoize)
 
    return ans
 
# Driver Code
if __name__ == '__main__':
    s = "4806"
 
    print(countDivBy6(s))
 
# This code is contributed by PranchalK

C#

// C# program to calculate number of substring
// divisible by 6.
using System;
 
class GFG
{
 
    static int MAX = 100002;
 
    // Return the number of substring divisible by 6
    // and starting at index i in s[] and previous sum
    // of digits modulo 3 is m.
    static int f(int i, int m, char []s, int [,]memoize)
    {
        // End of the string.
        if (i == s.Length)
        {
            return 0;
        }
 
        // If already calculated, return the
        // stored value.
        if (memoize[i,m] != -1)
        {
            return memoize[i,m];
        }
 
        // Converting into integer.
        int x = s[i] - '0';
 
        // Increment result by 1, if current digit
        // is divisible by 2 and sum of digits is
        // divisible by 3.
        // And recur for next index with new modulo.
        int ans = ((((x + m) % 3 == 0) && (x % 2 == 0)) ? 1 : 0)
                + f(i + 1, (m + x) % 3, s, memoize);
 
        return memoize[i,m] = ans;
    }
 
    // Returns substrings divisible by 6.
    static int countDivBy6(char []s)
    {
        int n = s.Length;
 
        // For storing the value of all states.
        int[,] memoize = new int[n + 1,3];
        for (int i = 0; i < n + 1; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                memoize[i,j] = -1;
            }
        }
 
        int ans = 0;
        for (int i = 0; i < s.Length; i++)
        {
            // If string contain 0, increment count by 1.
            if (s[i] == '0')
            {
                ans++;
            }
            // Else calculate using recursive function.
            // Pass previous sum modulo 3 as 0.
            else
            {
                ans += f(i, 0, s, memoize);
            }
        }
 
        return ans;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        char []s = "4806".ToCharArray();
 
        Console.WriteLine(countDivBy6(s));
    }
}
 
/* This code is contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript program to calculate number
// of substring
 
// Return the number of substring divisible
// by 6 and starting at index i in s[] and
// previous sum of digits modulo 3 is m.
function f(i, m, s, memoize){
     
    // End of the string.
    if (i == s.length)
        return 0
 
    // If already calculated, return
    // the stored value.
    if (memoize[i][m] != -1)
        return memoize[i][m]
 
    // Converting into integer.
    let x = s.charCodeAt(i) - '0'.charCodeAt(0)
 
    // Increment result by 1, if current digit
    // is divisible by 2 and sum of digits is
    // divisible by 3.
    // And recur for next index with new modulo.
    ans = (((x + m) % 3 == 0 && x % 2 == 0) + f(i + 1, (m + x) % 3, s, memoize))
 
    memoize[i][m] = ans
    return memoize[i][m]
}
 
// Returns substrings divisible by 6.
function countDivBy6(s){
    let n = s.length
 
    // For storing the value of all states.
    let memoize = new Array(n + 1)
    for(let i=0;i<n + 1;i++){
        memoize[i] = new Array(3).fill(-1)
    }
 
    let ans = 0
    for(let i=0;i<s.length;i++){
         
        // If string contain 0, increment
        // count by 1.
        if (s[i] == '0')
            ans += 1
 
        // Else calculate using recursive function.
        // Pass previous sum modulo 3 as 0.
        else
            ans += f(i, 0, s, memoize)
    }
 
    return ans
}
 
// Driver Code
 
let    s = "4806"
document.write(countDivBy6(s))
 
// This code is contributed by shinjanpatra
 
</script>
Producción

5

Complejidad temporal: O(n). 
Espacio Auxiliar: O(n) 

Este artículo es una contribución de Aarti_Rathi y 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.

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *