Recuento de enteros del rango [0, N] cuya suma de dígitos es un múltiplo de K

Dados dos números enteros N y K , la tarea es calcular el número de números enteros en el rango [0, N] cuya suma de dígitos es un múltiplo de K . La respuesta podría ser grande, así que imprime la respuesta módulo 10 9 +7 .

Ejemplos:  

Entrada: N = 10, K = 5 
Salida:
0 y 5 son los únicos números enteros posibles.

Entrada: N = 30, K = 4 
Salida: 7  

Enfoque ingenuo: para un valor pequeño de N , recorra el rango [0, N] y verifique si la suma de los dígitos de los números son múltiplos de K o no.
 

Enfoque eficiente: la idea es usar digit dp para resolver este problema. Los subproblemas que iteran a través de todos los valores de índice desde la izquierda o el dígito más significativo (MSD) en el entero dado se resolverán y para cada índice, almacene el número de formas tales que (suma de dígitos hasta el índice actual) mod K sea cero. Los estados de dp serán: 

dp[idx][sum][tight] 
idx = posición, informa sobre el valor del índice desde la izquierda en el entero dado 
suma = suma de dígitos mod k, este parámetro almacenará la (suma de dígitos mod k) en el entero generado desde el dígito más significativo (MSD) hasta p 
apretado = marca si el valor actual está cruzando el rango (1, n) o no 
Para rango sin restricciones apretado = 0 
Para rango restringido apretado = 1 

Digamos que estamos en el MSD que tiene el índice idx . Así que inicialmente la suma será 0 . En cada posición, establezca un límite que siempre esté en el rango [0, 9]
Por lo tanto, complete el dígito en el índice con los dígitos en su rango de 0 a límite y obtenga la respuesta del siguiente estado que tenga índice = idx + 1 y new_tight para el siguiente estado se calcula por separado. La definición de estado de dp será: 

dp[idx][sum][tight] += dp[idx + 1][(sum + d) % k][new_tight] 
para d en [0, límite]  

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 100005
#define MOD 1000000007
 
// To store the states of the dp
int dp[MAX][101][2];
 
// Function to return the count of numbers
// from the range [0, n] whose digit sum
// is a multiple of k using bottom-up dp
int countNum(int idx, int sum, int tight,
             vector<int> num, int len, int k)
{
    if (len == idx) {
        if (sum == 0)
            return 1;
        else
            return 0;
    }
    if (dp[idx][sum][tight] != -1)
        return dp[idx][sum][tight];
    int res = 0, limit;
 
    // The digit in this index can
    // only be from [0, num[idx]]
    if (tight == 0) {
        limit = num[idx];
    }
 
    // The digit in this index can
    // be anything from [0, 9]
    else {
        limit = 9;
    }
    for (int i = 0; i <= limit; i++) {
 
        // new_tight is the flag value
        // for the next position
        int new_tight = tight;
        if (tight == 0 && i < limit)
            new_tight = 1;
        res += countNum(idx + 1,
                        (sum + i) % k, new_tight,
                        num, len, k);
        res %= MOD;
    }
 
    // res can't be negative
    if (res < 0)
        res += MOD;
    return dp[idx][sum][tight] = res;
}
 
// Function to process the string to
// a vector of digits from MSD to LSD
vector<int> process(string s)
{
    vector<int> num;
    for (int i = 0; i < s.length(); i++) {
        num.push_back(s[i] - '0');
    }
    return num;
}
 
// Driver code
int main()
{
 
    // For large input number n
    string n = "98765432109876543210";
 
    // Total number of digits in n
    int len = n.length();
 
    int k = 58;
 
    // Clean dp table
    memset(dp, -1, sizeof(dp));
 
    // Process the string to a vector
    // of digits from MSD to LSD
    vector<int> num = process(n);
 
    cout << countNum(0, 0, 0, num, len, k);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
static final int MAX = 100005;
static final int MOD = 1000000007;
 
// To store the states of the dp
static int [][][]dp = new int[MAX][101][2];
 
// Function to return the count of numbers
// from the range [0, n] whose digit sum
// is a multiple of k using bottom-up dp
static int countNum(int idx, int sum, int tight,
            Vector<Integer> num, int len, int k)
{
    if (len == idx)
    {
        if (sum == 0)
            return 1;
        else
            return 0;
    }
    if (dp[idx][sum][tight] != -1)
        return dp[idx][sum][tight];
    int res = 0, limit;
 
    // The digit in this index can
    // only be from [0, num[idx]]
    if (tight == 0)
    {
        limit = num.get(idx);
    }
 
    // The digit in this index can
    // be anything from [0, 9]
    else
    {
        limit = 9;
    }
    for (int i = 0; i <= limit; i++)
    {
 
        // new_tight is the flag value
        // for the next position
        int new_tight = tight;
        if (tight == 0 && i < limit)
            new_tight = 1;
        res += countNum(idx + 1,
                        (sum + i) % k, new_tight,
                        num, len, k);
        res %= MOD;
    }
 
    // res can't be negative
    if (res < 0)
        res += MOD;
    return dp[idx][sum][tight] = res;
}
 
// Function to process the String to
// a vector of digits from MSD to LSD
static Vector<Integer> process(String s)
{
    Vector<Integer> num = new Vector<Integer>();
    for (int i = 0; i < s.length(); i++)
    {
        num.add(s.charAt(i) - '0');
    }
    return num;
}
 
// Driver code
public static void main(String[] args)
{
 
    // For large input number n
    String n = "98765432109876543210";
 
    // Total number of digits in n
    int len = n.length();
 
    int k = 58;
 
    // Clean dp table
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j < 101; j++)
        {
            for(int l = 0; l < 2; l++)
            dp[i][j][l] = -1;
        }
    }
 
    // Process the String to a vector
    // of digits from MSD to LSD
    Vector<Integer> num = process(n);
 
    System.out.print(countNum(0, 0, 0, num, len, k));
 
}
}
 
// This code is contributed by 29AjayKumar

Python 3

# Python 3 implementation of the approach
MAX = 10005
MOD = 1000000007
 
# Function to return the count of numbers
# from the range [0, n] whose digit sum
# is a multiple of k using bottom-up dp
def countNum(idx, sum, tight, num, len1, k):
    if (len1 == idx):
        if (sum == 0):
            return 1
        else:
            return 0
    if (dp[idx][sum][tight] != -1):
        return dp[idx][sum][tight]
    res = 0
 
    # The digit in this index can
    # only be from [0, num[idx]]
    if (tight == 0):
        limit = num[idx]
 
    # The digit in this index can
    # be anything from [0, 9]
    else:
        limit = 9
    for i in range(limit + 1):
         
        # new_tight is the flag value
        # for the next position
        new_tight = tight
        if (tight == 0 and i < limit):
            new_tight = 1
        res += countNum(idx + 1,(sum + i) % k,
                      new_tight, num, len1, k)
        res %= MOD
 
    # res can't be negative
    if (res < 0):
        res += MOD
    dp[idx][sum][tight] = res
    return dp[idx][sum][tight]
 
# Function to process the string to
# a vector of digits from MSD to LSD
def process(s):
    num = []
    for i in range(len(s)):
        num.append(ord(s[i]) - ord('0'))
    return num
 
# Driver code
if __name__ == '__main__':
     
    # For large input number n
    n = "98765432109876543210"
 
    # Total number of digits in n
    len1 = len(n)
 
    k = 58
     
    # To store the states of the dp
    dp = [[[-1 for i in range(2)]
               for j in range(101)]
               for k in range(MAX)]
 
    # Process the string to a vector
    # of digits from MSD to LSD
    num = process(n)
 
    print(countNum(0, 0, 0, num, len1, k))
 
# This code is contributed by Surendra_Gangwar

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
static readonly int MAX = 10005;
static readonly int MOD = 1000000007;
 
// To store the states of the dp
static int [,,]dp = new int[MAX, 101, 2];
 
// Function to return the count of numbers
// from the range [0, n] whose digit sum
// is a multiple of k using bottom-up dp
static int countNum(int idx, int sum, int tight,
              List<int> num, int len, int k)
{
    if (len == idx)
    {
        if (sum == 0)
            return 1;
        else
            return 0;
    }
     
    if (dp[idx, sum, tight] != -1)
        return dp[idx, sum, tight];
    int res = 0, limit;
 
    // The digit in this index can
    // only be from [0, num[idx]]
    if (tight == 0)
    {
        limit = num[idx];
    }
 
    // The digit in this index can
    // be anything from [0, 9]
    else
    {
        limit = 9;
    }
    for (int i = 0; i <= limit; i++)
    {
 
        // new_tight is the flag value
        // for the next position
        int new_tight = tight;
        if (tight == 0 && i < limit)
            new_tight = 1;
        res += countNum(idx + 1,
                       (sum + i) % k, new_tight,
                        num, len, k);
        res %= MOD;
    }
 
    // res can't be negative
    if (res < 0)
        res += MOD;
    return dp[idx, sum, tight] = res;
}
 
// Function to process the String to
// a vector of digits from MSD to LSD
static List<int> process(String s)
{
    List<int> num = new List<int>();
    for (int i = 0; i < s.Length; i++)
    {
        num.Add(s[i] - '0');
    }
    return num;
}
 
// Driver code
public static void Main(String[] args)
{
 
    // For large input number n
    String n = "98765432109876543210";
 
    // Total number of digits in n
    int len = n.Length;
 
    int k = 58;
 
    // Clean dp table
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j < 101; j++)
        {
            for(int l = 0; l < 2; l++)
            dp[i, j, l] = -1;
        }
    }
 
    // Process the String to a vector
    // of digits from MSD to LSD
    List<int> num = process(n);
 
    Console.Write(countNum(0, 0, 0, num, len, k));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
var MAX = 100005;
var MOD = 1000000007;
 
// To store the states of the dp
var dp = Array.from(Array(MAX), () => Array(101));
for(var i =0; i<MAX; i++)
        for(var j =0; j<101; j++)
            dp[i][j] = new Array(2).fill(-1);
 
// Function to return the count of numbers
// from the range [0, n] whose digit sum
// is a multiple of k using bottom-up dp
function countNum(idx, sum, tight, num, len, k)
{
    if (len == idx) {
        if (sum == 0)
            return 1;
        else
            return 0;
    }
    if (dp[idx][sum][tight] != -1)
        return dp[idx][sum][tight];
    var res = 0, limit;
 
    // The digit in this index can
    // only be from [0, num[idx]]
    if (tight == 0) {
        limit = num[idx];
    }
 
    // The digit in this index can
    // be anything from [0, 9]
    else {
        limit = 9;
    }
    for (var i = 0; i <= limit; i++) {
 
        // new_tight is the flag value
        // for the next position
        var new_tight = tight;
        if (tight == 0 && i < limit)
            new_tight = 1;
        res += countNum(idx + 1,
                        (sum + i) % k, new_tight,
                        num, len, k);
        res %= MOD;
    }
 
    // res can't be negative
    if (res < 0)
        res += MOD;
    return dp[idx][sum][tight] = res;
}
 
// Function to process the string to
// a vector of digits from MSD to LSD
function process(s)
{
    var num = [];
    for (var i = 0; i < s.length; i++) {
        num.push(s[i].charCodeAt(0) - '0'.charCodeAt(0));
    }
    return num;
}
 
// Driver code
// For large input number n
var n = "98765432109876543210";
// Total number of digits in n
var len = n.length;
var k = 58;
// Process the string to a vector
// of digits from MSD to LSD
var num = process(n);
document.write( countNum(0, 0, 0, num, len, k));
 
</script>
Producción: 

635270835

 

Publicación traducida automáticamente

Artículo escrito por ShrabanaBiswas 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 *