Dado un rango representado por dos números enteros positivos L y R y un número entero positivo K. Encuentra el conteo de números en el rango donde el número no contiene más de K dígitos distintos de cero.
Ejemplos:
Input : L = 1, R = 1000, K = 3 Output : 1000 Explanation : All the numbers from 1 to 1000 are 3 digit numbers which obviously cannot contain more than 3 non zero digits. Input : L = 9995, R = 10005 Output : 6 Explanation : Required numbers are 10000, 10001, 10002, 10003, 10004 and 10005
Requisitos previos: Digit DP
Puede haber dos enfoques para resolver este tipo de problema, uno puede ser una solución combinatoria y otro puede ser una solución basada en programación dinámica. A continuación se muestra un enfoque detallado para resolver este problema utilizando un enfoque de programación dinámica de dígitos.
Solución de programación dinámica: 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 el conteo que define el número de dígitos distintos de cero que hemos colocado en el número que estamos tratando de construir.
- 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.
En la llamada recursiva final, cuando estamos en la última posición si el recuento de dígitos distintos de cero es menor o igual a K, devuelve 1; de lo contrario, devuelve 0.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP Program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
#include <bits/stdc++.h>
using namespace std;
const int M = 20;
// states - position, count, tight
int dp[M][M][2];
// K is the number of non zero digits
int K;
// This function returns the count of
// required numbers from 0 to num
int countInRangeUtil(int pos, int cnt, int tight,
vector<int> num)
{
// Last position
if (pos == num.size()) {
// If count of non zero digits
// is less than or equal to K
if (cnt <= K)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][cnt][tight] != -1)
return dp[pos][cnt][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 dig = 0; dig <= limit; dig++) {
int currCnt = cnt;
// If the current digit is nonzero
// increment currCnt
if (dig != 0)
currCnt++;
int currTight = tight;
// At this position, number becomes
// smaller
if (dig < num[pos])
currTight = 1;
// Next recursive call
ans += countInRangeUtil(pos + 1, currCnt,
currTight, num);
}
return dp[pos][cnt][tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to compute
// the answer
int countInRange(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 countInRangeUtil(0, 0, 0, num);
}
// Driver Code to test above functions
int main()
{
int L = 1, R = 1000;
K = 3;
cout << countInRange(R) - countInRange(L - 1) << endl;
L = 9995, R = 10005, K = 2;
cout << countInRange(R) - countInRange(L - 1) << endl;
return 0;
}
Java
// Java Program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
import java.util.*;
class Solution
{
static final int M = 20;
// states - position, count, tight
static int dp[][][]= new int[M][M][2];
// K is the number of non zero digits
static int K;
static Vector<Integer> num;
// This function returns the count of
// required numbers from 0 to num
static int countInRangeUtil(int pos, int cnt, int tight )
{
// Last position
if (pos == num.size()) {
// If count of non zero digits
// is less than or equal to K
if (cnt <= K)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][cnt][tight] != -1)
return dp[pos][cnt][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 dig = 0; dig <= limit; dig++) {
int currCnt = cnt;
// If the current digit is nonzero
// increment currCnt
if (dig != 0)
currCnt++;
int currTight = tight;
// At this position, number becomes
// smaller
if (dig < num.get(pos))
currTight = 1;
// Next recursive call
ans += countInRangeUtil(pos + 1, currCnt, currTight);
}
return dp[pos][cnt][tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to compute
// the answer
static int countInRange(int x)
{
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<M;j++)
for(int k=0;k<2;k++)
dp[i][j][k]=-1;
return countInRangeUtil(0, 0, 0);
}
// Driver Code to test above functions
public static void main(String args[])
{
int L = 1, R = 1000;
K = 3;
System.out.println( countInRange(R) - countInRange(L - 1) );
L = 9995; R = 10005; K = 2;
System.out.println( countInRange(R) - countInRange(L - 1) );
}
}
//contributed by Arnab Kundu
Python3
# Python Program to find the count of # numbers in a range where the number # does not contain more than K non # zero digits # This function returns the count of # required numbers from 0 to num def countInRangeUtil(pos, cnt, tight, num): # Last position if pos == len(num): # If count of non zero digits # is less than or equal to K if cnt <= K: return 1 return 0 # If this result is already computed # simply return it if dp[pos][cnt][tight] != -1: return dp[pos][cnt][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] limit = 9 if tight else num[pos] for dig in range(limit + 1): currCnt = cnt # If the current digit is nonzero # increment currCnt if dig != 0: currCnt += 1 currTight = tight # At this position, number becomes # smaller if dig < num[pos]: currTight = 1 # Next recursive call ans += countInRangeUtil(pos + 1, currCnt, currTight, num) dp[pos][cnt][tight] = ans return dp[pos][cnt][tight] # This function converts a number into its # digit vector and uses above function to compute # the answer def countInRange(x): global dp, K, M num = [] while x: num.append(x % 10) x //= 10 num.reverse() # Initialize dp dp = [[[-1, -1] for i in range(M)] for j in range(M)] return countInRangeUtil(0, 0, 0, num) # Driver Code if __name__ == "__main__": # states - position, count, tight dp = [] M = 20 # K is the number of non zero digits K = 0 L = 1 R = 1000 K = 3 print(countInRange(R) - countInRange(L - 1)) L = 9995 R = 10005 K = 2 print(countInRange(R) - countInRange(L - 1)) # This code is contributed by # sanjeev2552
C#
// C# Program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
using System;
using System.Collections.Generic;
class GFG
{
static int M = 20;
// states - position, count, tight
static int [,,]dp = new int[M, M, 2];
// K is the number of non zero digits
static int K;
static List<int> num;
// This function returns the count of
// required numbers from 0 to num
static int countInRangeUtil(int pos,
int cnt, int tight )
{
// Last position
if (pos == num.Count)
{
// If count of non zero digits
// is less than or equal to K
if (cnt <= K)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos, cnt, tight] != -1)
return dp[pos, cnt, 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 dig = 0; dig <= limit; dig++)
{
int currCnt = cnt;
// If the current digit is nonzero
// increment currCnt
if (dig != 0)
currCnt++;
int currTight = tight;
// At this position, number becomes
// smaller
if (dig < num[pos])
currTight = 1;
// Next recursive call
ans += countInRangeUtil(pos + 1, currCnt, currTight);
}
return dp[pos,cnt,tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to compute
// the answer
static int countInRange(int x)
{
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 < M; j++)
for(int k = 0; k < 2; k++)
dp[i, j, k] = -1;
return countInRangeUtil(0, 0, 0);
}
// Driver Code
public static void Main()
{
int L = 1, R = 1000;
K = 3;
Console.WriteLine( countInRange(R) - countInRange(L - 1) );
L = 9995; R = 10005; K = 2;
Console.WriteLine( countInRange(R) - countInRange(L - 1) );
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript Program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
let M = 20;
// states - position, count, tight
let dp = new Array(M);
for(let i = 0; i < M; i++)
{
dp[i] = new Array(M);
for(let j = 0; j < M; j++)
{
dp[i][j] = new Array(2);
for(let k = 0; k < 2; k++)
dp[i][j][k] = 0;
}
}
// K is the number of non zero digits
let K;
let num;
// This function returns the count of
// required numbers from 0 to num
function countInRangeUtil(pos, cnt, tight )
{
// Last position
if (pos == num.length)
{
// If count of non zero digits
// is less than or equal to K
if (cnt <= K)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][cnt][tight] != -1)
return dp[pos][cnt][tight];
let 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]
let limit = (tight!=0 ? 9 : num[pos]);
for (let dig = 0; dig <= limit; dig++) {
let currCnt = cnt;
// If the current digit is nonzero
// increment currCnt
if (dig != 0)
currCnt++;
let currTight = tight;
// At this position, number becomes
// smaller
if (dig < num[pos])
currTight = 1;
// Next recursive call
ans += countInRangeUtil(pos + 1, currCnt, currTight);
}
return dp[pos][cnt][tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to compute
// the answer
function countInRange(x)
{
num= [];
while (x!=0) {
num.push(x % 10);
x = Math.floor(x/10);
}
num.reverse();
// Initialize dp
for(let i=0;i<M;i++)
for(let j=0;j<M;j++)
for(let k=0;k<2;k++)
dp[i][j][k]=-1;
return countInRangeUtil(0, 0, 0);
}
// Driver Code to test above functions
let L = 1, R = 1000;
K = 3;
document.write( (countInRange(R) - countInRange(L - 1)) +"<br>");
L = 9995; R = 10005; K = 2;
document.write( (countInRange(R) - countInRange(L - 1)) +"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1000 6
Complejidad de tiempo: O (M * M * 2 * 10) donde M = log (MAX), aquí MAX es el número máximo.
Espacio auxiliar: O(M*M)
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