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 4. La substring puede contener ceros a la izquierda.
Ejemplos:
Input : "124" Output : 4 Substrings divisible by 4 are "12", "4", "24", "124" . Input : "04" Output : 3 Substring divisible by 4 are "0", "4", "04" .
Método 1: (Fuerza bruta) La idea es encontrar todas las substrings de la string dada y verificar si la substring es divisible por 4 o no.
Tiempo Complejidad: O(
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
).
Solución eficiente: un número es divisible por 4 si sus dos últimos dígitos son divisibles por 4 y los números de un solo dígito divisibles por 4 son 4, 8 y 0. Entonces, para calcular el número de substrings divisibles por 4, primero contamos el número de 0 , 4’s y 8’s en la cuerda. Luego, hacemos todos los pares de dos caracteres consecutivos y los convertimos en un número entero. Después de convertirlo en entero, verificamos si es divisible por 4 o no. Si es divisible por 4, entonces todas las substrings que terminan con estos dos últimos caracteres son divisibles por 4. Ahora, el número de tales substrings es básicamente el índice del primer carácter del par.. Para que quede más claro, considere la string «14532465», luego los pares posibles son «14», «45», «53», «32», «24», «46», «65». En estos pares, solo «32» y «24» cuando se convierten en enteros son divisibles por 4. Entonces, las substrings (longitud >= 2) divisibles por 4 deben terminar con «32» o «24». Entonces, el número de substrings que terminan con “32” son “14532”, “4532”, “532”, “32”, es decir, 4 y el índice de ‘3’ también es 4. De manera similar, el número de substrings que terminan en «24» es 5.
Así obtenemos una solución O(n). A continuación se muestra la implementación de este enfoque.
C++
// C++ program to count number of substrings
// divisible by 4.
#include <bits/stdc++.h>
using namespace std;
int countDivisbleby4(char s[])
{
int n = strlen(s);
// In the first loop we will count number of
// 0's, 4's and 8's present in the string
int count = 0;
for (int i = 0; i < n; ++i)
if (s[i] == '4' || s[i] == '8' || s[i] == '0')
count++ ;
// In second loop we will convert pairs
// of two consecutive characters into
// integer and store it in variable h .
// Then we check whether h is divisible by 4
// or not . If h is divisible we increases
// the count with ( i + 1 ) as index of
// first character of pair
for (int i = 0; i < n - 1; ++i) {
int h = ( s[i] - '0' ) * 10 + ( s[i+1] - '0' );
if (h % 4 == 0)
count = count + i + 1 ;
}
return count;
}
// Driver code to test above function
int main()
{
char s[] = "124";
cout << countDivisbleby4(s);
return 0;
}
Java
// Java program to count number of substrings
// divisible by 4
import java.io.*;
class GFG
{
// Function to count number of substrings
// divisible by 4
static int countDivisbleby4(String s)
{
int n = s.length();
// In the first loop we will count number of
// 0's, 4's and 8's present in the string
int count = 0;
for (int i = 0; i < n; ++i)
if (s.charAt(i) == '4' || s.charAt(i) == '8' || s.charAt(i) == '0')
count++ ;
// In second loop we will convert pairs
// of two consecutive characters into
// integer and store it in variable h .
// Then we check whether h is divisible by 4
// or not . If h is divisible we increases
// the count with ( i + 1 ) as index of
// first character of pair
for (int i = 0; i < n - 1; ++i)
{
int h = ( s.charAt(i) - '0' ) * 10 + ( s.charAt(i+1) - '0' );
if (h % 4 == 0)
count = count + i + 1 ;
}
return count;
}
// driver program
public static void main (String[] args)
{
String s = "124";
System.out.println(countDivisbleby4(s));
}
}
// Contributed by Pramod Kumar
Python3
# Python3 program to count the number of substrings
# divisible by 4.
def countDivisbleby4(s):
n = len(s)
# In the first loop we will count number of
# 0's, 4's and 8's present in the string
count = 0;
for i in range(0,n,1):
if (s[i] == '4' or s[i] == '8' or s[i] == '0'):
count += 1
# In second loop we will convert pairs
# of two consecutive characters into
# integer and store it in variable h .
# Then we check whether h is divisible by 4
# or not . If h is divisible we increases
# the count with ( i + 1 ) as index of
# first character of pair
for i in range(0,n - 1,1):
h = (ord(s[i]) - ord('0')) * 10 + (ord(s[i+1]) - ord('0'))
if (h % 4 == 0):
count = count + i + 1
return count
# Driver code to test above function
if __name__ == '__main__':
s = ['1','2','4']
print(countDivisbleby4(s))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to count number of
// substrings divisible by 4
using System;
public class GFG
{
// Function to count number of
// substrings divisible by 4
static int countDivisbleby4(string s)
{
int n = s.Length;
// In the first loop we will count
// number of 0's, 4's and 8's present
// in the string
int count = 0;
for (int i = 0; i < n; ++i)
if (s[i] == '4' || s[i] == '8'
|| s[i] == '0')
count++ ;
// In second loop we will convert pairs
// of two consecutive characters into
// integer and store it in variable h .
// Then we check whether h is divisible
// by 4 or not . If h is divisible, we
// increases the count with ( i + 1 )
// as index of first character of pair
for (int i = 0; i < n - 1; ++i)
{
int h = (s[i] - '0' ) * 10 +
(s[i + 1] - '0' );
if (h % 4 == 0)
count = count + i + 1 ;
}
return count;
}
// Driver Code
public static void Main ()
{
string s = "124";
Console.WriteLine(countDivisbleby4(s));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count number
// of substrings divisible by 4.
function countDivisbleby4( $s)
{
$n = strlen($s);
// In the first loop we
// will count number of
// 0's, 4's and 8's present
// in the string
$count = 0;
for($i = 0; $i < $n; ++$i)
if ($s[$i] == '4' or $s[$i] == '8'
or $s[$i] == '0')
$count++ ;
// In second loop we will convert pairs
// of two consecutive characters into
// integer and store it in variable h .
// Then we check whether h is divisible by 4
// or not . If h is divisible we increases
// the count with ( i + 1 ) as index of
// first character of pair
for ( $i = 0; $i < $n - 1; ++$i)
{
$h = ( $s[$i] - '0' ) * 10 +
( $s[$i+1] - '0' );
if ($h % 4 == 0)
$count = $count + $i + 1 ;
}
return $count;
}
// Driver Code
$s = "124";
echo countDivisbleby4($s);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to count number
// of substrings divisible by 4.
function countDivisbleby4(s)
{
let n = s.length;
// In the first loop we
// will count number of
// 0's, 4's and 8's present
// in the string
let count = 0;
for(let i = 0; i < n; ++i)
if (s[i] == '4' || s[i] == '8' ||
s[i] == '0')
count++;
// In second loop we will convert pairs
// of two consecutive characters into
// integer and store it in variable h .
// Then we check whether h is divisible by 4
// or not . If h is divisible we increases
// the count with ( i + 1 ) as index of
// first character of pair
for(let i = 0; i < n - 1; ++i)
{
let h = (s[i] - '0') * 10 +
(s[i + 1] - '0');
if (h % 4 == 0)
count = count + i + 1 ;
}
return count;
}
// Driver Code
let s = "124";
document.write(countDivisbleby4(s));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
4
Este artículo es una contribución de Surya Priy . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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