Contar números de N dígitos con suma divisible por K

Dados dos números enteros N y K , la tarea es contar todos los números de N dígitos cuya suma de dígitos sea divisible por K .

Ejemplos:

Entrada: N = 2, K = 7
Salida: 12
Explicación: Los números de 2 dígitos con suma divisible por 7 son: {16, 25, 34, 43, 52, 59, 61, 68, 70, 77, 86, 95}.
Por lo tanto, la salida requerida es 12.

Entrada: N = 1, K = 2
Salida: 4

Enfoque ingenuo: el enfoque más simple es recorrer todos los números del rango [10 ^{(N – 1)} , 10 ^N – 1] y verificar si la suma de todos los dígitos de un número que se encuentra dentro del rango es divisible por K o no. Por cada número para el cual la condición se cumpla, aumente la cuenta . Finalmente, imprima el conteo .

Complejidad de Tiempo: O(10 ^N – 10 ^{N – 1} – 1)
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea es utilizar la técnica Digit DP para optimizar el enfoque anterior. A continuación se muestra la relación de recurrencia:

$CountNum(N, sum, st) = \sum^{9}_{i=0} countNum(N - 1, (sum + i)\mod K, st)$

sum: representa la suma de dígitos
st: verifica si un número contiene algún 0 inicial.

Siga los pasos a continuación para resolver el problema:

Inicialice una array 3D dp[N][K][st] para calcular y almacenar los valores de todos los subproblemas de la relación de recurrencia anterior.
Finalmente, devuelva el valor de dp[N][sum%K][st] .

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define M 1000
 
// Function to count the N digit numbers
// whose sum is divisible by K
int countNum(int N, int sum, int K,
             bool st, int dp[M][M][2])
{
    // Base case
    if (N == 0 and sum == 0) {
        return 1;
    }
    if (N < 0) {
        return 0;
    }
 
    // If already computed
    // subproblem occurred
    if (dp[N][sum][st] != -1) {
        return dp[N][sum][st];
    }
 
    // Store the count of N digit numbers
    // whose sum is divisible by K
    int res = 0;
 
    // Check if the number does not contain
    // any leading 0.
    int start = st == 1 ? 0 : 1;
 
    // Recurrence relation
    for (int i = start; i <= 9; i++) {
        res += countNum(N - 1, (sum + i) % K,
                        K, (st | i > 0), dp);
    }
 
    return dp[N][sum][st] = res;
}
 
// Driver Code
int main()
{
    int N = 2, K = 7;
 
    // Stores the values of
    // overlapping subproblems
    int dp[M][M][2];
 
    memset(dp, -1, sizeof(dp));
 
    cout << countNum(N, 0, K, 0, dp);
}

Java

// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
 
class GFG {
 
    static final int M = 1000;
 
    // Function to count the N digit numbers
    // whose sum is divisible by K
    static int countNum(int N, int sum, int K,
                        int st, int dp[][][])
    {
 
        // Base case
        if (N == 0 && sum == 0) {
            return 1;
        }
        if (N < 0) {
            return 0;
        }
 
        // If already computed
        // subproblem occurred
        if (dp[N][sum][st] != -1) {
            return dp[N][sum][st];
        }
 
        // Store the count of N digit numbers
        // whose sum is divisible by K
        int res = 0;
 
        // Check if the number does not contain
        // any leading 0.
        int start = st == 1 ? 0 : 1;
 
        // Recurrence relation
        for (int i = start; i <= 9; i++) {
            res += countNum(N - 1, (sum + i) % K,
                            K, ((st | i) > 0) ? 1 : 0, dp);
        }
        return dp[N][sum][st] = res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 2, K = 7;
 
        // Stores the values of
        // overlapping subproblems
        int[][][] dp = new int[M][M][2];
 
        for (int[][] i : dp)
            for (int[] j : i)
                Arrays.fill(j, -1);
 
        System.out.print(countNum(N, 0, K, 0, dp));
    }
}
 
// This code is contributed by offbeat

Python3

# Python3 program to implement
# the above approach
 
# Function to count the N digit
# numbers whose sum is divisible by K
def countNum(N, sum, K, st, dp):
     
    # Base case
    if (N == 0 and sum == 0):
        return 1
 
    if (N < 0):
        return 0
 
    # If already computed
    # subproblem occurred
    if (dp[N][sum][st] != -1):
        return dp[N][sum][st]
 
    # Store the count of N digit
    # numbers whose sum is divisible by K
    res = 0
    start = 1
     
    # Check if the number does not contain
    # any leading 0.
    if (st == 1):
        start = 0
    else:
        start = 1
 
    # Recurrence relation
    for i in range(start, 10):
        min = 0
         
        if ((st | i) > 0):
            min = 1
        else:
            min = 0
             
        res += countNum(N - 1, (sum + i) % K,
                        K, min, dp)
        dp[N][sum][st] = res
         
    return dp[N][sum][st]
 
# Driver code
if __name__ == '__main__':
     
    N = 2
    K = 7
    M = 100
     
    # Stores the values of
    # overlapping subproblems
    dp = [[[-1 for i in range(2)]
               for j in range(M)]
               for j in range(M)]
 
    print(countNum(N, 0, K, 0, dp))
 
# This code is contributed by shikhasingrajput

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
     
static int M = 1000;
 
// Function to count the N digit numbers
// whose sum is divisible by K
static int countNum(int N, int sum, int K,
                    int st, int[,, ] dp)
{
     
    // Base case
    if (N == 0 && sum == 0)
    {
        return 1;
    }
    if (N < 0)
    {
        return 0;
    }
 
    // If already computed
    // subproblem occurred
    if (dp[N, sum, st] != -1)
    {
        return dp[N, sum, st];
    }
 
    // Store the count of N digit numbers
    // whose sum is divisible by K
    int res = 0;
 
    // Check if the number does not contain
    // any leading 0.
    int start = (st == 1 ? 0 : 1);
     
    // Recurrence relation
    for(int i = start; i <= 9; i++)
    {
        res += countNum(N - 1, (sum + i) % K,
                        K, ((st | i) > 0) ? 1 : 0, dp);
    }
    return dp[N, sum, st] = res;
}
 
// Driver code
static public void Main()
{
    int N = 2, K = 7;
     
    // Stores the values of
    // overlapping subproblems
    int[,, ] dp = new int[M, M, 2];
 
    for(int i = 0; i < M; i++)
        for(int j = 0; j < M; j++)
            for(int k = 0; k < 2; k++)
                dp[i, j, k] = -1;
 
    Console.WriteLine(countNum(N, 0, K, 0, dp));
}
}
 
// This code is contributed by offbeat

Javascript

<script>
 
// JavaScript Program to implement
// the above approach
 
var M = 1000;
 
// Function to count the N digit numbers
// whose sum is divisible by K
function countNum(N, sum, K, st, dp)
{
    // Base case
    if (N == 0 && sum == 0) {
        return 1;
    }
    if (N < 0) {
        return 0;
    }
 
    // If already computed
    // subproblem occurred
    if (dp[N][sum][st] != -1) {
        return dp[N][sum][st];
    }
 
    // Store the count of N digit numbers
    // whose sum is divisible by K
    var res = 0;
 
    // Check if the number does not contain
    // any leading 0.
    var start = st == 1 ? 0 : 1;
 
    // Recurrence relation
    for (var i = start; i <= 9; i++) {
        res += countNum(N - 1, (sum + i) % K,
                        K, (st | i > 0), dp);
    }
 
    return dp[N][sum][st] = res;
}
 
// Driver Code
 
var N = 2, K = 7;
 
// Stores the values of
// overlapping subproblems
var dp = Array.from(Array(M), ()=>Array(M));
for(var i =0; i<M; i++)
        for(var j =0; j<M; j++)
            dp[i][j] = new Array(2).fill(-1);
document.write( countNum(N, 0, K, 0, dp));
 
 
</script>

Producción:

Complejidad de tiempo: O(10*N*K)

Espacio Auxiliar: O(N*K)

Publicación traducida automáticamente

Artículo escrito por ayushnemmaniwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta