Recuento de números entre rangos que solo tienen dígitos distintos de cero cuya suma de dígitos es N y el número es divisible por M

Dado un rango [L, R] y dos enteros positivos N y M . La tarea es contar los números en el rango que contiene solo dígitos distintos de cero cuya suma de dígitos es igual a N y el número es divisible por M .
Ejemplos: 
 

Entrada: L = 1, R = 100, N = 8, M = 2 
Salida:
Solo 8, 26, 44 y 62 son números válidos 
Entrada: L = 1, R = 200, N = 4, M = 11 
Salida:
Solo 22 y 121 son números válidos 
 

Prerrequisitos: Dígito DP
 

Enfoque: en primer lugar, si podemos contar los números requeridos hasta R, es decir, en el rango [0, R], podemos llegar fácilmente a nuestra respuesta en el rango [L, R] resolviendo de cero a R y luego restando la respuesta que obtenemos después de resolver de cero a L – 1. Ahora, necesitamos definir los estados de DP. 
Estados DP
 

  • Dado que podemos considerar nuestro número como una secuencia de dígitos, un estado es la posición en la que nos encontramos actualmente. Esta posición puede tener valores de 0 a 18 si estamos tratando con números hasta 10 18 . En cada llamada recursiva, tratamos de construir la secuencia de izquierda a derecha colocando un dígito del 0 al 9.
  • El segundo estado es la suma de los dígitos que hemos colocado hasta ahora.
  • El tercer estado es el resto que define el módulo del número que hemos hecho hasta ahora módulo M.
  • Otro estado es la variable booleana tight que indica que el número que estamos tratando de construir ya se ha vuelto más pequeño que R, de modo que en las próximas llamadas recursivas podemos colocar cualquier dígito del 0 al 9. Si el número no se ha vuelto más pequeño, el límite máximo de dígito que podemos colocar es dígito en la posición actual en R.

Para que el número tenga solo dígitos distintos de cero, mantenemos una variable noz cuyo valor si 1 le dice que el primer dígito del número que hemos colocado es un dígito distinto de cero y, por lo tanto, ahora no podemos colocar ningún dígito cero en el próximo llamadas De lo contrario, podemos colocar un dígito cero como cero inicial para que el número de dígitos en el número actual sea menor que el número de dígitos en el límite superior.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int M = 20;
 
// states - position, sum, rem, tight
// sum can have values upto 162, if we
// are dealing with numbers upto 10^18
// when all 18 digits are 9, then sum
// is 18 * 9 = 162
int dp[M][165][M][2];
 
// n is the sum of digits and number should
// be divisible by m
int n, m;
 
// Function to return the count of
// required numbers from 0 to num
int count(int pos, int sum, int rem, int tight,
          int nonz, vector<int> num)
{
    // Last position
    if (pos == num.size()) {
        if (rem == 0 && sum == n)
            return 1;
        return 0;
    }
 
    // If this result is already computed
    // simply return it
    if (dp[pos][sum][rem][tight] != -1)
        return dp[pos][sum][rem][tight];
 
    int ans = 0;
 
    // Maximum limit upto which we can place
    // digit. If tight is 1, means number has
    // already become smaller so we can place
    // any digit, otherwise num[pos]
    int limit = (tight ? 9 : num[pos]);
 
    for (int d = 0; d <= limit; d++) {
 
        // If the current digit is zero
        // and nonz is 1, we can't place it
        if (d == 0 && nonz)
            continue;
        int currSum = sum + d;
        int currRem = (rem * 10 + d) % m;
        int currF = tight || (d < num[pos]);
        ans += count(pos + 1, currSum, currRem,
                     currF, nonz || d, num);
    }
    return dp[pos][sum][rem][tight] = ans;
}
 
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
int solve(int x)
{
    vector<int> num;
    while (x) {
        num.push_back(x % 10);
        x /= 10;
    }
    reverse(num.begin(), num.end());
 
    // Initialize dp
    memset(dp, -1, sizeof(dp));
    return count(0, 0, 0, 0, 0, num);
}
 
// Driver code
int main()
{
    int L = 1, R = 100;
    n = 8, m = 2;
    cout << solve(R) - solve(L);
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
static int M = 20;
 
// states - position, sum, rem, tight
// sum can have values upto 162, if we
// are dealing with numbers upto 10^18
// when all 18 digits are 9, then sum
// is 18 * 9 = 162
static int dp[][][][] = new int [M][165][M][2];
 
// n is the sum of digits and number should
// be divisible by m
static int n, m;
 
// Function to return the count of
// required numbers from 0 to num
static int count(int pos, int sum, int rem, int tight,
        int nonz, Vector<Integer> num)
{
    // Last position
    if (pos == num.size())
    {
        if (rem == 0 && sum == n)
            return 1;
        return 0;
    }
 
    // If this result is already computed
    // simply return it
    if (dp[pos][sum][rem][tight] != -1)
        return dp[pos][sum][rem][tight];
 
    int ans = 0;
 
    // Maximum limit upto which we can place
    // digit. If tight is 1, means number has
    // already become smaller so we can place
    // any digit, otherwise num[pos]
    int limit = (tight != 0 ? 9 : num.get(pos));
 
    for (int d = 0; d <= limit; d++)
    {
 
        // If the current digit is zero
        // and nonz is 1, we can't place it
        if (d == 0 && nonz != 0)
            continue;
        int currSum = sum + d;
        int currRem = (rem * 10 + d) % m;
        int currF = (tight != 0 || (d < num.get(pos))) ? 1 : 0;
        ans += count(pos + 1, currSum, currRem,
                    currF, (nonz != 0 || d != 0) ? 1 : 0, num);
    }
    return dp[pos][sum][rem][tight] = ans;
}
 
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
static int solve(int x)
{
    Vector<Integer> num = new Vector<Integer>();
    while (x != 0)
    {
        num.add(x % 10);
        x /= 10;
    }
    Collections.reverse(num);
 
    // Initialize dp
    for(int i = 0; i < M; i++)
        for(int j = 0; j < 165; j++)
            for(int k = 0; k < M; k++)
                for(int l = 0; l < 2; l++)
                    dp[i][j][k][l]=-1;
     
    return count(0, 0, 0, 0, 0, num);
}
 
// Driver code
public static void main(String args[])
{
    int L = 1, R = 100;
    n = 8; m = 2;
    System.out.print( solve(R) - solve(L));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach
 
# Function to return the count of
# required numbers from 0 to num
def count(pos, Sum, rem, tight, nonz, num):
 
    # Last position
    if pos == len(num):
        if rem == 0 and Sum == n:
            return 1
        return 0
 
    # If this result is already computed
    # simply return it
    if dp[pos][Sum][rem][tight] != -1:
        return dp[pos][Sum][rem][tight]
     
    ans = 0
 
    # Maximum limit upto which we can place
    # digit. If tight is 1, means number has
    # already become smaller so we can place
    # any digit, otherwise num[pos]
    if tight:
        limit = 9
    else:
        limit = num[pos]
     
    for d in range(0, limit + 1):
 
        # If the current digit is zero
        # and nonz is 1, we can't place it
        if d == 0 and nonz:
            continue
             
        currSum = Sum + d
        currRem = (rem * 10 + d) % m
        currF = int(tight or (d < num[pos]))
        ans += count(pos + 1, currSum, currRem,
                     currF, nonz or d, num)
     
    dp[pos][Sum][rem][tight] = ans
    return ans
 
# Function to convert x into its digit
# vector and uses count() function to
# return the required count
def solve(x):
 
    num = []
    global dp
     
    while x > 0:
        num.append(x % 10)
        x //= 10
     
    num.reverse()
 
    # Initialize dp
    dp = [[[[-1, -1] for i in range(M)]
                     for j in range(165)]
                     for k in range(M)]
    return count(0, 0, 0, 0, 0, num)
 
# Driver code
if __name__ == "__main__":
 
    L, R = 1, 100
     
    # n is the sum of digits and number
    # should be divisible by m
    n, m, M = 8, 2, 20
     
    # States - position, sum, rem, tight
    # sum can have values upto 162, if we
    # are dealing with numbers upto 10^18
    # when all 18 digits are 9, then sum
    # is 18 * 9 = 162
    dp = []
 
    print(solve(R) - solve(L))
     
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
static int M = 20;
 
// states - position, sum, rem, tight
// sum can have values upto 162, if we
// are dealing with numbers upto 10^18
// when all 18 digits are 9, then sum
// is 18 * 9 = 162
static int [,,,]dp = new int [M, 165, M, 2];
 
// n is the sum of digits and number should
// be divisible by m
static int n, m;
 
// Function to return the count of
// required numbers from 0 to num
static int count(int pos, int sum, int rem, int tight,
                            int nonz, List<int> num)
{
    // Last position
    if (pos == num.Count)
    {
        if (rem == 0 && sum == n)
            return 1;
        return 0;
    }
 
    // If this result is already computed
    // simply return it
    if (dp[pos,sum,rem,tight] != -1)
        return dp[pos,sum,rem,tight];
 
    int ans = 0;
 
    // Maximum limit upto which we can place
    // digit. If tight is 1, means number has
    // already become smaller so we can place
    // any digit, otherwise num[pos]
    int limit = (tight != 0 ? 9 : num[pos]);
 
    for (int d = 0; d <= limit; d++)
    {
 
        // If the current digit is zero
        // and nonz is 1, we can't place it
        if (d == 0 && nonz != 0)
            continue;
        int currSum = sum + d;
        int currRem = (rem * 10 + d) % m;
        int currF = (tight != 0 || (d < num[pos])) ? 1 : 0;
        ans += count(pos + 1, currSum, currRem,
                    currF, (nonz != 0 || d != 0) ? 1 : 0, num);
    }
    return dp[pos, sum, rem, tight] = ans;
}
 
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
static int solve(int x)
{
    List<int> num = new List<int>();
    while (x != 0)
    {
        num.Add(x % 10);
        x /= 10;
    }
    num.Reverse();
 
    // Initialize dp
    for(int i = 0; i < M; i++)
        for(int j = 0; j < 165; j++)
            for(int k = 0; k < M; k++)
                for(int l = 0; l < 2; l++)
                    dp[i, j, k, l] = -1;
     
    return count(0, 0, 0, 0, 0, num);
}
 
// Driver code
public static void Main(String []args)
{
    int L = 1, R = 100;
    n = 8; m = 2;
    Console.Write( solve(R) - solve(L));
}
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript implementation of the approach
 
var M = 20;
 
// states - position, sum, rem, tight
// sum can have values upto 162, if we
// are dealing with numbers upto 10^18
// when all 18 digits are 9, then sum
// is 18 * 9 = 162
var dp = Array.from(Array(M), ()=>Array(165));
 
// n is the sum of digits and number should
// be divisible by m
var n, m;
 
// Function to return the count of
// required numbers from 0 to num
function count( pos, sum, rem, tight, nonz, num)
{
    // Last position
    if (pos == num.length) {
        if (rem == 0 && sum == n)
            return 1;
        return 0;
    }
    // If this result is already computed
    // simply return it
    if (dp[pos][sum][rem][tight] != -1)
        return dp[pos][sum][rem][tight];
 
    var ans = 0;
 
    // Maximum limit upto which we can place
    // digit. If tight is 1, means number has
    // already become smaller so we can place
    // any digit, otherwise num[pos]
    var limit = (tight ? 9 : num[pos]);
 
    for (var d = 0; d <= limit; d++) {
 
        // If the current digit is zero
        // and nonz is 1, we can't place it
        if (d == 0 && nonz)
            continue;
        var currSum = sum + d;
        var currRem = (rem * 10 + d) % m;
        var currF = (tight != 0 || (d < num[pos])) ? 1 : 0;
        ans += count(pos + 1, currSum, currRem,
                    currF, (nonz != 0 || d != 0) ? 1 : 0, num);
    }
    dp[pos][sum][rem][tight] = ans;
    return ans;
}
 
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
function solve(x)
{
    var num = [];
    while (x) {
        num.push(x % 10);
        x = parseInt(x/10);
    }
    num.reverse();
 
    // Initialize dp
    for(var i =0; i<M; i++)
        for(var j =0; j<165; j++)
            dp[i][j] = Array.from(Array(M), ()=>Array(2).fill(-1));
    return count(0, 0, 0, 0, 0, num);
}
 
// Driver code
var L = 1, R = 100;
n = 8, m = 2;
document.write( solve(R) - solve(L));
 
</script>
Producción: 

4

 

Complejidad temporal: O(M*M)
Espacio auxiliar: O(M*M)

Implementación corta de Python: 
 

Python3

# User Input
l, r, n, m = 1, 100, 8, 2
 
# Initialize Result
output = []
 
# Traverse through all numbers
for x in range(l, r+1):
 
    # Check for all conditions in every number
    if sum([int(k) for k in str(x)]) == n and x % m == 0 and '0' not in str(x): # Check conditions
        output.append(x)
  
print(len(output)) 
  
# This code is contributed by mailprakashindia

Publicación traducida automáticamente

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