Dado un entero K y una string numérica str (todos los caracteres son del rango [‘0’, ‘9’] ). La tarea es contar el número de substrings de str que son divisibles por K .
Ejemplos:
Entrada: str = «33445», K = 11
Salida: 3 substrings
que son divisibles por 11 son «33», «44» y «3344»Entrada: str = “334455”, K = 11
Salida: 6
Enfoque: Inicializar cuenta = 0 . Tome todas las substrings de str y verifique si son divisibles por K o no. En caso afirmativo, actualice count = count + 1 . Imprime el conteo al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of sub-strings
// of str that are divisible by k
int countSubStr(string str, int len, int k)
{
int count = 0;
for (int i = 0; i < len; i++)
{
int n = 0;
// Take all sub-strings starting from i
for (int j = i; j < len; j++)
{
n = n * 10 + (str[j] - '0');
// If current sub-string is divisible by k
if (n % k == 0)
count++;
}
}
// Return the required count
return count;
}
// Driver code
int main()
{
string str = "33445";
int len = str.length();
int k = 11;
cout << countSubStr(str, len, k);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to return the count of sub-strings
// of str that are divisible by k
static int countSubStr(String str, int len, int k)
{
int count = 0;
for (int i = 0; i < len; i++)
{
int n = 0;
// Take all sub-strings starting from i
for (int j = i; j < len; j++)
{
n = n * 10 + (str.charAt(j) - '0');
// If current sub-string is divisible by k
if (n % k == 0)
count++;
}
}
// Return the required count
return count;
}
// Driver code
public static void main(String []args)
{
String str = "33445";
int len = str.length();
int k = 11;
System.out.println(countSubStr(str, len, k));
}
}
// This code is contributed by Ryuga
Python3
# Python 3 implementation of the approach
# Function to return the count of sub-strings
# of str that are divisible by k
def countSubStr(str, l, k):
count = 0
for i in range(l):
n = 0
# Take all sub-strings starting from i
for j in range(i, l, 1):
n = n * 10 + (ord(str[j]) - ord('0'))
# If current sub-string is divisible by k
if (n % k == 0):
count += 1
# Return the required count
return count
# Driver code
if __name__ == '__main__':
str = "33445"
l = len(str)
k = 11
print(countSubStr(str, l, k))
# This code is contributed by
# Sanjit_Prasad
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the count of sub-strings
// of str that are divisible by k
static int countSubStr(String str, int len, int k)
{
int count = 0;
for (int i = 0; i < len; i++)
{
int n = 0;
// Take all sub-strings starting from i
for (int j = i; j < len; j++)
{
n = n * 10 + (str[j] - '0');
// If current sub-string is divisible by k
if (n % k == 0)
count++;
}
}
// Return the required count
return count;
}
// Driver code
public static void Main()
{
String str = "33445";
int len = str.Length;
int k = 11;
Console.WriteLine(countSubStr(str, len, k));
}
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP implementation of the approach
// Function to return the count of sub-strings
// of str that are divisible by k
function countSubStr($str, $len, $k)
{
$count = 0;
for ($i = 0; $i < $len; $i++)
{
$n = 0;
// Take all sub-strings starting from i
for ($j = $i; $j < $len; $j++)
{
$n = $n * 10 + ($str[$j] - '0');
// If current sub-string is
// divisible by k
if ($n % $k == 0)
$count++;
}
}
// Return the required count
return $count;
}
// Driver code
$str = "33445";
$len = strlen($str);
$k = 11;
echo countSubStr($str, $len, $k);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to return the count of sub-strings
// of str that are divisible by k
function countSubStr(str, len, k)
{
let count = 0;
for(let i = 0; i < len; i++)
{
let n = 0;
// Take all sub-strings starting from i
for(let j = i; j < len; j++)
{
n = n * 10 + (str[j].charCodeAt() -
'0'.charCodeAt());
// If current sub-string is
// divisible by k
if (n % k == 0)
count++;
}
}
// Return the required count
return count;
}
// Driver code
let str = "33445";
let len = str.length;
let k = 11;
document.write(countSubStr(str, len, k));
// This code is contributed by mukesh07
</script>
Producción
3
Enfoque eficiente:
La idea es usar un hashMap para almacenar los restos de cada sufijo de la string, de modo que cualquier sufijo, si ya está presente en el hashMap, entonces la substring entre ellos es divisible por k.
A continuación se muestra la implementación del enfoque anterior.
Java
// Java Program for above approach
import java.util.*;
public class Main
{
// Program to count number of substrings
public static int Divisible(String s,
int k)
{
// To count substrings
int num_of_substrings = 0;
// To store the remainders
int rem[] = new int[k];
rem[0] = 1;
StringBuffer curr = new StringBuffer();
// Iterate from s.length() - 1 to 0
for (int i = s.length() - 1; i >= 0; i--)
{
// to Calculate suffix string
curr.insert(0, s.charAt(i));
// convert to number
long num = Long.parseLong(curr.
toString());
num_of_substrings += rem[(int)num % k];
// Keep track of visited remainders
rem[(int)num % k]++;
}
// Return number of substrings
return num_of_substrings;
}
// Driver Code
public static void main(String args[])
{
String s = "111111";
int k = 11;
// Function Call
System.out.println("Number of sub strings : "
+ Divisible(s, k));
}
}
C#
// C# Program for above approach
using System;
using System.Text;
public class GFG
{
// Program to count number of substrings
public static int Divisible(string s,
int k)
{
// To count substrings
int num_of_substrings = 0;
// To store the remainders
int[] rem = new int[k];
rem[0] = 1;
StringBuilder curr = new StringBuilder();
// Iterate from s.length() - 1 to 0
for (int i = s.Length - 1; i >= 0; i--)
{
// to Calculate suffix string
curr.Insert(0, s[i]);
// convert to number
long num = Convert.ToInt64(Convert.ToString(curr));
num_of_substrings += rem[(int)num % k];
// Keep track of visited remainders
rem[(int)num % k]++;
}
// Return number of substrings
return num_of_substrings;
}
// Driver Code
public static void Main(string[] args)
{
string s = "111111";
int k = 11;
// Function Call
Console.WriteLine("Number of sub strings : "
+ Divisible(s, k));
}
}
// This code is contributed by phasing17
Producción
Number of sub strings : 9
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(k)
Publicación traducida automáticamente
Artículo escrito por Mukund Agarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA