Tenemos que contar el número de subcadenas de una cadena dada que es divisible por 3.
Entrada: 130 Salida: 3
Entrada: 303 Salida: 6
- ¿Habría algún límite matemático potencial para una máquina física con el propósito de replicarse a sí mismo?
- En la universidad, ¿debería centrarme más en la teoría o la aplicación en los campos de la informática y las matemáticas?
- ¿Cómo se puede lograr acceso aleatorio en O (log n)?
- ¿Cómo se puede encontrar el logaritmo de base 10 de un número de hasta 5 decimales con solo usar las cuatro operaciones básicas (+, -, *, /) con la ayuda de una calculadora?
- ¿Cuáles son las formas o tipos de problemas en los que XOR es útil?
Entrada: 2014 Salida: 2
Entrada: 2012 Salida: 4
Explicación:
Caso 1:
3
0 0
30
Caso 2:
3
0 0
3
30
03
303
Caso 3:
0 0
201
Caso 4:
0 0
12
201
012
Enfoque de solución:
Al principio veamos cómo calcular subcadenas. Supongamos que tenemos una cadena ‘ abc ‘ y tenemos que encontrar todas las subcadenas de ‘ abc ‘. Entonces en:
Posición 0
una
Posición 1
si
ab
Posición 2
do
antes de Cristo
a B C
Por lo tanto, podemos ver fácilmente que en cada posición / carácter, este carácter se puede concatenar con subcadenas anteriores y este carácter en sí mismo es una subcadena. Entonces no. de subcadenas que termina en una posición particular es igual a no. de subcadenas termina en la posición anterior + 1 . Ahora sumamos acumulativamente este valor en cada posición para obtener el no total. de subcadena para la cadena dada. Ahora, en nuestro caso, podemos decir que una subcadena termina en una posición particular es divisible por 3 si contiene un residuo de ‘0’ (módulo 3) en esta posición. Entonces iremos a cada posición y calcularemos no. de subcadenas = x con un residuo de 0 (módulo 3) luego agregaremos este valor (x) acumulativamente para calcular el no. de subcadenas que termina con un residuo de 0 (módulo 3) que es divisible por 3.
Tomemos la entrada como una cadena ‘ str ‘, en cada carácter tenemos un residuo de ‘ r ‘, es decir r = (str [i] – ‘0’)% 3 que es el valor de r está en el rango 0, 1 y 2) Supongamos que tenemos dos matrices, a saber, residuo y anterior_residuo . El residuo [i] contiene el número de subcadenas que termina en el carácter actual con un residuo i, y previous_residue [i] contiene el número de subcadenas que termina en el carácter anterior con el residuo i. Entonces, si agregamos un número de subcadenas que termina en un carácter / posición con un residuo 0, tendremos nuestra solución sumando todas ellas de forma acumulativa.
Ahora tengamos un residuo de ‘0’ para el carácter actual que es (str [i] – ‘0’)% 3 = 0, entonces ahora tenemos una subcadena adicional (el carácter actual) con residuo 0 y no. de las subcadenas termina en la posición i con el residuo 1 y el residuo 2 será el mismo. Entonces podemos escribir:
residuo [0] = residuo_ anterior [0] + 1.
residuo [1] = residuo_ anterior [1].
residuo [2] = residuo_ anterior [2].
Si tenemos el residuo ‘1’ para el carácter actual, entonces el número de subcadenas termina en el carácter anterior con el residuo 0 ahora tendrá el residuo 1, el número de subcadenas con el residuo 1 en el carácter anterior tendrá el residuo 2 y el número de las subcadenas con el residuo 2 ahora tendrán el residuo 0. Y ahora tenemos una subcadena adicional (el carácter actual) con el residuo 1. Para que podamos escribir:
residuo [0] = residuo_ anterior [2].
residuo [1] = residuo_ anterior [0] + 1.
residuo [2] = residuo_ anterior [1].
Si tenemos el residuo ‘2’ para el carácter actual, entonces el número de subcadenas termina en el carácter anterior con el residuo 0 tendrá el residuo 2, el número de subcadenas con el residuo 1 en el carácter anterior tendrá el residuo 0 y el número de sub -las cadenas con el residuo 2 ahora tendrán el residuo 1. Y ahora tenemos una subcadena adicional (el carácter actual) con el residuo 2. Para que podamos escribir:
residuo [0] = residuo_ anterior [1].
residuo [1] = residuo_ anterior [2].
residuo [2] = residuo_ anterior [0] + 1.
Ahora fusionando esto podemos escribir:
residuo [0] = residuo_ anterior [(3 – r + 0)% 3].
residuo [1] = residuo_ anterior [(3 – r + 1)% 3].
residuo [2] = residuo_ anterior [(3 – r + 2)% 3].
residuo [r] = residuo [r] + 1.
Ahora, en cada posición, solo tenemos que contar cuántas subcadenas terminan en esta posición con el residuo 0 , y tomamos ese valor incluido en nuestra respuesta. Y simplemente copiaremos nuestra matriz ‘ residual ‘ a nuestra matriz ‘ previous_residue ‘ para usar en el siguiente paso. Entonces el pseudocódigo puede verse así:
total = 0;
residuo [3] = {0, 0, 0};
anterior_residuo [3] = {0, 0, 0};
para (i = 0; i <longitud de str; i ++)
{
r = (str [i] – ‘0’)% 3;
para (j = 0; j <3; j ++)
residuo [j] = residuo_ anterior [(3 – r + j)% 3];
residuo [r] = residuo [r] + 1;
total + = residuo [0];
para (j = 0; j <3; j ++)
anterior_residuo [j] = residuo [j];
}
impresión (total);
