Dados dos enteros positivos N y K , la tarea es contar el número de enteros positivos D tales que D tenga N dígitos y cualquiera de los sufijos de su representación decimal sea divisible por K.
Ejemplos:
Entrada: N = 1, K = 2
Salida: 4
Explicación:
Hay 4 enteros en los que cualquiera de los sufijos es divisible por K:
{2, 4, 6, 8}Entrada: N = 2, K = 2
Salida: 45
Explicación:
Hay 45, números enteros de dos dígitos en los que cualquiera de los sufijos es divisible por 2:
algunos de esos números enteros se dan a continuación:
{10, 12, 13, 14, 15 , 16, 18, 19, 20, 21, 22, 23…}
Observe que los números 21 y 23 no son divisibles por 2. Pero su sufijo 2 es divisible por 2.
Enfoque ingenuo: iterar sobre todos los números enteros del dígito N y para cada número entero verificar que cualquier sufijo del número sea divisible por K. Si es así, entonces incrementar el conteo de dichos números en 1. Enfoque: la idea es usar
el concepto de Programación Dinámica aumentando la longitud del sufijo y colocando los dígitos del 0 al 9 de forma recursiva . A continuación se muestra la ilustración de los pasos:
- Definición de la función: Este problema se puede resolver recursivamente en el que, en cada paso, podemos elegir los dígitos para el sufijo del número de N dígitos. Entonces, la definición de función de la solución recursiva será:
// Recursive Function to count of values // whose suffixes of length pos // have remainder rem with K recur(pos, rem)
- Caso base: el caso base de este problema es cuando, para cualquier índice, el resto del sufijo con K se convierte en 0, entonces todos los demás dígitos se pueden colocar con todos los enteros posibles del 0 al 9.
f(pos, 0) = 9 * (10^(n-i-1))
- Caso recursivo: en cada paso de la recursión aumentamos la longitud del sufijo en uno colocando todos los números enteros del 0 al 9, cambiamos el resto con K en consecuencia y pasamos al siguiente paso.
for num in range [0-9]:
f(pos, rem) += f(pos+1, (rem*10 + num)%k)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Count the
// numbers with N digits and whose
// suffix is divisible by K
#include <bits/stdc++.h>
using namespace std;
int mod = 1000000007;
int dp[1005][105][2];
int powers[1005];
int powersModk[1005];
// Suffix of length pos with
// remainder rem and Z representing
// whether the suffix has a
// non zero digit until now
int calculate(int pos, int rem,
int z, int k, int n)
{
// Base case
if (rem == 0 && z) {
// If count of digits
// is less than n
if (pos != n)
// Placing all possible
// digits in remaining
// positions
return (powers[n - pos -
1] * 9) % mod;
else
return 1;
}
// If remainder non zero
// and suffix has n digits
if (pos == n)
return 0;
// If the subproblem
// is already solved
if (dp[pos][rem][z] != -1)
return dp[pos][rem][z];
int count = 0;
// Placing all digits at MSB
// of suffix and increasing
// it's length by 1
for (int i = 0; i < 10; i++) {
if (i == 0)
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, z, k, n))) % mod;
// Non zero digit is placed
else
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, 1, k, n))) % mod;
}
// Store and return the
// solution to this subproblem
return dp[pos][rem][z] = count;
}
// Function to Count the numbers
// with N digits and whose suffix
// is divisible by K
int countNumbers(int n, int k)
{
// Since we need powers of 10
// for counting, it's better to
// pre store them along with their
// modulo with 1e9 + 7 for counting
int st = 1;
for (int i = 0; i <= n; i++) {
powers[i] = st;
st *= 10;
st %= mod;
}
// Since at each recursive step
// we increase the suffix length by 1
// by placing digits at its leftmost
// position, we need powers of 10
// modded with k, in order to fpos
// the new remainder efficiently
st = 1;
for (int i = 0; i <= n; i++) {
powersModk[i] = st;
st *= 10;
st %= mod;
}
// Initialising dp table values -1
// represents subproblem hasn't
// been solved yet
memset(dp, -1, sizeof(dp));
return calculate(0, 0, 0, k, n);
}
// Driver Code
int main()
{
int N = 2;
int K = 2;
cout << countNumbers(N, K);
return 0;
}
Java
// Java implementation to Count the
// numbers with N digits and whose
// suffix is divisible by K
import java.util.*;
import java.util.Arrays;
class GFG
{
static int mod = 1000000007;
static int dp[][][] = new int[1005][105][2];
static int powers[] = new int[1005];
static int powersModk[] = new int[1005];
// Suffix of length pos with
// remainder rem and Z representing
// whether the suffix has a
// non zero digit until now
static int calculate(int pos, int rem,
int z, int k, int n)
{
// Base case
if (rem == 0 && z!=0) {
// If count of digits
// is less than n
if (pos != n)
// Placing all possible
// digits in remaining
// positions
return (powers[n - pos -
1] * 9) % mod;
else
return 1;
}
// If remainder non zero
// and suffix has n digits
if (pos == n)
return 0;
// If the subproblem
// is already solved
if (dp[pos][rem][z] != -1)
return dp[pos][rem][z];
int count = 0;
// Placing all digits at MSB
// of suffix and increasing
// it's length by 1
for (int i = 0; i < 10; i++) {
if (i == 0)
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, z, k, n))) % mod;
// Non zero digit is placed
else
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, 1, k, n))) % mod;
}
// Store and return the
// solution to this subproblem
return dp[pos][rem][z] = count;
}
// Function to Count the numbers
// with N digits and whose suffix
// is divisible by K
static int countNumbers(int n, int k)
{
// Since we need powers of 10
// for counting, it's better to
// pre store them along with their
// modulo with 1e9 + 7 for counting
int st = 1;
int i;
for (i = 0; i <= n; i++) {
powers[i] = st;
st *= 10;
st %= mod;
}
// Since at each recursive step
// we increase the suffix length by 1
// by placing digits at its leftmost
// position, we need powers of 10
// modded with k, in order to fpos
// the new remainder efficiently
st = 1;
for (i = 0; i <= n; i++) {
powersModk[i] = st;
st *= 10;
st %= mod;
}
// Initialising dp table values -1
// represents subproblem hasn't
// been solved yet
for (int[][] row: dp)
{
for (int[] innerRow: row)
{
Arrays.fill(innerRow, -1);
}
};
return calculate(0, 0, 0, k, n);
}
// Driver Code
public static void main(String []args)
{
int N = 2;
int K = 2;
System.out.print(countNumbers(N, K));
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation to Count the # numbers with N digits and whose # suffix is divisible by K mod = 1000000007 dp = [[[-1 for i in range(2)] for i in range(105)] for i in range(1005)] powers = [0]*1005 powersModk = [0]*1005 # Suffix of length pos with # remainder rem and Z representing # whether the suffix has a # non zero digit until now def calculate(pos, rem, z, k, n): # Base case if (rem == 0 and z): # If count of digits # is less than n if (pos != n): # Placing all possible # digits in remaining # positions return (powers[n - pos -1] * 9) % mod else: return 1 # If remainder non zero # and suffix has n digits if (pos == n): return 0 # If the subproblem # is already solved if (dp[pos][rem][z] != -1): return dp[pos][rem][z] count = 0 # Placing all digits at MSB # of suffix and increasing # it's length by 1 for i in range(10): if (i == 0): count = (count + (calculate( pos + 1, (rem + (i * powersModk[pos]) % k) % k, z, k, n))) % mod # Non zero digit is placed else: count = (count + (calculate( pos + 1, (rem + (i * powersModk[pos]) % k) % k, 1, k, n))) % mod # Store and return the # solution to this subproblem dp[pos][rem][z] = count return count # Function to Count the numbers # with N digits and whose suffix # is divisible by K def countNumbers(n, k): # Since we need powers of 10 # for counting, it's better to # pre store them along with their # modulo with 1e9 + 7 for counting st = 1 for i in range(n + 1): powers[i] = st st *= 10 st %= mod # Since at each recursive step # we increase the suffix length by 1 # by placing digits at its leftmost # position, we need powers of 10 # modded with k, in order to fpos # the new remainder efficiently st = 1 for i in range(n + 1): powersModk[i] = st st *= 10 st %= mod # Initialising dp table values -1 # represents subproblem hasn't # been solved yet # memset(dp, -1, sizeof(dp)) return calculate(0, 0, 0, k, n) # Driver Code if __name__ == '__main__': N = 2 K = 2 print(countNumbers(N, K)) # This code is contributed by mohit kumar 29
C#
// C# implementation to Count the
// numbers with N digits and whose
// suffix is divisible by K
using System;
class GFG
{
static int mod = 1000000007;
static int [,,]dp = new int[1005, 105, 2];
static int []powers = new int[1005];
static int []powersModk = new int[1005];
// Suffix of length pos with
// remainder rem and Z representing
// whether the suffix has a
// non zero digit until now
static int calculate(int pos, int rem,
int z, int k, int n)
{
// Base case
if (rem == 0 && z != 0) {
// If count of digits
// is less than n
if (pos != n)
// Placing all possible
// digits in remaining
// positions
return (powers[n - pos -
1] * 9) % mod;
else
return 1;
}
// If remainder non zero
// and suffix has n digits
if (pos == n)
return 0;
// If the subproblem
// is already solved
if (dp[pos, rem, z] != -1)
return dp[pos,rem,z];
int count = 0;
// Placing all digits at MSB
// of suffix and increasing
// it's length by 1
for (int i = 0; i < 10; i++) {
if (i == 0)
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, z, k, n))) % mod;
// Non zero digit is placed
else
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, 1, k, n))) % mod;
}
// Store and return the
// solution to this subproblem
return dp[pos,rem,z] = count;
}
// Function to Count the numbers
// with N digits and whose suffix
// is divisible by K
static int countNumbers(int n, int k)
{
// Since we need powers of 10
// for counting, it's better to
// pre store them along with their
// modulo with 1e9 + 7 for counting
int st = 1;
int i;
for (i = 0; i <= n; i++) {
powers[i] = st;
st *= 10;
st %= mod;
}
// Since at each recursive step
// we increase the suffix length by 1
// by placing digits at its leftmost
// position, we need powers of 10
// modded with k, in order to fpos
// the new remainder efficiently
st = 1;
for (i = 0; i <= n; i++) {
powersModk[i] = st;
st *= 10;
st %= mod;
}
// Initialising dp table values -1
// represents subproblem hasn't
// been solved yet
for(i = 0; i < 1005; i++){
for(int j = 0; j < 105; j++){
for(int l = 0; l < 2; l++)
dp[i, j, l] = -1;
}
}
return calculate(0, 0, 0, k, n);
}
// Driver Code
public static void Main(String []args)
{
int N = 2;
int K = 2;
Console.Write(countNumbers(N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to Count the
// numbers with N digits and whose
// suffix is divisible by K
var mod = 1000000007;
var dp = Array.from(Array(1005), ()=>Array(105));
for(var i = 0; i< 1005; i++)
{
for(var j =0; j<105; j++)
{
dp[i][j] = Array(2).fill(-1);
}
}
var powers = Array(1005);
var powersModk= Array(1005);
// Suffix of length pos with
// remainder rem and Z representing
// whether the suffix has a
// non zero digit until now
function calculate(pos, rem, z, k, n)
{
// Base case
if (rem == 0 && z) {
// If count of digits
// is less than n
if (pos != n)
// Placing all possible
// digits in remaining
// positions
return (powers[n - pos -
1] * 9) % mod;
else
return 1;
}
// If remainder non zero
// and suffix has n digits
if (pos == n)
return 0;
// If the subproblem
// is already solved
if (dp[pos][rem][z] != -1)
return dp[pos][rem][z];
var count = 0;
// Placing all digits at MSB
// of suffix and increasing
// it's length by 1
for (var i = 0; i < 10; i++) {
if (i == 0)
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, z, k, n))) % mod;
// Non zero digit is placed
else
count = (count + (calculate(
pos + 1, (rem + (i *
powersModk[pos]) % k) %
k, 1, k, n))) % mod;
}
// Store and return the
// solution to this subproblem
return dp[pos][rem][z] = count;
}
// Function to Count the numbers
// with N digits and whose suffix
// is divisible by K
function countNumbers(n, k)
{
// Since we need powers of 10
// for counting, it's better to
// pre store them along with their
// modulo with 1e9 + 7 for counting
var st = 1;
for (var i = 0; i <= n; i++) {
powers[i] = st;
st *= 10;
st %= mod;
}
// Since at each recursive step
// we increase the suffix length by 1
// by placing digits at its leftmost
// position, we need powers of 10
// modded with k, in order to fpos
// the new remainder efficiently
st = 1;
for (var i = 0; i <= n; i++) {
powersModk[i] = st;
st *= 10;
st %= mod;
}
return calculate(0, 0, 0, k, n);
}
// Driver Code
var N = 2;
var K = 2;
document.write( countNumbers(N, K));
</script>
Producción:
45
Complejidad temporal: O(N * K)
Espacio auxiliar: O (1005 * 105 * 2)