Dado un número entero N y un conjunto de dígitos D[] , que consta de dígitos de [1, 9]. La tarea es contar los números posibles menores que N , cuyos dígitos son del conjunto de dígitos dado.
Ejemplos:
Entrada: D = [“1”, “4”, “9”], N = 10
Salida: 3
Explicación:
Solo hay 3 números posibles menos de 3 con un conjunto dado de dígitos:
1, 4, 9Entrada: D[] = {“1”, “3”, “5”, “7”}, N = 100
Salida: 20
Explicación:
Solo hay 20 números posibles menos de 100 con el conjunto de dígitos dado:
1, 3 , 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Enfoque ingenuo: verifique los dígitos de todos los números del rango [1, N], si todos los dígitos de un número pertenecen al conjunto de dígitos dado, incremente el conteo en 1.
Enfoque Eficiente: La idea es usar el concepto de Dígito DP y recorrer el conjunto dado de dígitos y generar todos los números que son estrictamente menores que el número N dado. Escoger recursivamente el dígito para todas las posiciones posibles del número y pasar un variable booleana ajustada para verificar que al incluir ese dígito, el número cae dentro del rango dado o no.
Pensemos en el estado posible para el DP:
- pos : Informa sobre la posición del dígito a elegir, de modo que el número caiga en el rango dado.
- apretado : Esto nos ayudará a saber si los dígitos actuales están restringidos o no. Si los dígitos están restringidos, se puede elegir cualquier dígito del conjunto de dígitos dado. De lo contrario, los dígitos se pueden elegir en el rango [1, N[pos]].
- size : Indicará el número de dígitos a elegir.
A continuación se muestra la ilustración de la función recursiva:
- Caso base: El caso base para este problema será cuando la posición del dígito a elegir sea igual a la longitud de los dígitos a elegir, entonces solo hay un número posible que contiene los dígitos que se eligen hasta el momento.
if (position == countDigits(N))
return 1
- Caso recursivo: para generar el número en el rango dado, use la variable estrecha para elegir los dígitos posibles en el rango de la siguiente manera:
- Si el valor de tight es 0, denota que al incluir ese dígito, el número será menor que el rango dado.
- De lo contrario, si el valor de tight es 1, denota que al incluir ese dígito, dará un número mayor que el rango dado. Entonces podemos eliminar todas las permutaciones después de obtener un valor ajustado de 1 para evitar más llamadas recursivas.
- Almacene el recuento de los números posibles después de elegir cada dígito para cada posición.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
#include <bits/stdc++.h>
using namespace std;
int dp[15][2];
// Function to convert integer
// into the string
string convertToString(int num)
{
stringstream ss;
ss << num;
string s = ss.str();
return s;
}
// Recursive function to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
int calculate(int pos, int tight,
int D[], int sz, string& num)
{
// Base case
if (pos == num.length())
return 1;
// Condition when the subproblem
// is computed previously
if (dp[pos][tight] != -1)
return dp[pos][tight];
int val = 0;
// Condition when the number
// chosen till now is definitely
// smaller than the given number N
if (tight == 0) {
// Loop to traverse all the
// digits of the given set
for (int i = 0; i < sz; i++) {
if (D[i] < (num[pos] - '0')) {
val += calculate(pos + 1,
1, D, sz, num);
}
else if (D[i] == num[pos] - '0')
val += calculate(pos + 1,
tight, D, sz, num);
}
}
else {
// Loop to traverse all the
// digits from the given set
for (int i = 0; i < sz; i++) {
val += calculate(pos + 1,
tight, D, sz, num);
}
}
// Store the solution for
// current subproblem
return dp[pos][tight] = val;
}
// Function to count the numbers
// less than N from given set of digits
int countNumbers(int D[], int N, int sz)
{
// Converting the number to string
string num = convertToString(N);
int len = num.length();
// Initially no subproblem
// is solved till now
memset(dp, -1, sizeof(dp));
// Find the solution of all the
// number equal to the length of
// the given number N
int ans = calculate(0, 0, D, sz, num);
// Loop to find the number less in
// in the length of the given number
for (int i = 1; i < len; i++)
ans += calculate(i, 1, D, sz, num);
return ans;
}
// Driver Code
int main()
{
int sz = 3;
int D[sz] = { 1, 4, 9 };
int N = 10;
// Function Call
cout << countNumbers(D, N, sz);
return 0;
}
Java
// Java implementation to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
import java.util.*;
class GFG{
static int [][]dp = new int[15][2];
// Function to convert integer
// into the String
static String convertToString(int num)
{
return String.valueOf(num);
}
// Recursive function to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
static int calculate(int pos, int tight,
int D[], int sz, String num)
{
// Base case
if (pos == num.length())
return 1;
// Condition when the subproblem
// is computed previously
if (dp[pos][tight] != -1)
return dp[pos][tight];
int val = 0;
// Condition when the number
// chosen till now is definitely
// smaller than the given number N
if (tight == 0) {
// Loop to traverse all the
// digits of the given set
for (int i = 0; i < sz; i++) {
if (D[i] < (num.charAt(pos) - '0')) {
val += calculate(pos + 1,
1, D, sz, num);
}
else if (D[i] == num.charAt(pos) - '0')
val += calculate(pos + 1,
tight, D, sz, num);
}
}
else {
// Loop to traverse all the
// digits from the given set
for (int i = 0; i < sz; i++) {
val += calculate(pos + 1,
tight, D, sz, num);
}
}
// Store the solution for
// current subproblem
return dp[pos][tight] = val;
}
// Function to count the numbers
// less than N from given set of digits
static int countNumbers(int D[], int N, int sz)
{
// Converting the number to String
String num = convertToString(N);
int len = num.length();
// Initially no subproblem
// is solved till now
for (int i = 0; i < 15; i++)
for (int j = 0; j < 2; j++)
dp[i][j] = -1;
// Find the solution of all the
// number equal to the length of
// the given number N
int ans = calculate(0, 0, D, sz, num);
// Loop to find the number less in
// in the length of the given number
for (int i = 1; i < len; i++)
ans += calculate(i, 1, D, sz, num);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int sz = 3;
int D[] = { 1, 4, 9 };
int N = 10;
// Function Call
System.out.print(countNumbers(D, N, sz));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find the
# count of numbers possible less
# than N, such that every digit
# is from the given set of digits
import numpy as np;
dp = np.ones((15,2))*-1;
# Function to convert integer
# into the string
def convertToString(num) :
return str(num);
# Recursive function to find the
# count of numbers possible less
# than N, such that every digit
# is from the given set of digits
def calculate(pos,tight, D, sz, num) :
# Base case
if (pos == len(num)):
return 1;
# Condition when the subproblem
# is computed previously
if (dp[pos][tight] != -1) :
return dp[pos][tight];
val = 0;
# Condition when the number
# chosen till now is definitely
# smaller than the given number N
if (tight == 0) :
# Loop to traverse all the
# digits of the given set
for i in range(sz) :
if (D[i] < (ord(num[pos]) - ord('0'))) :
val += calculate(pos + 1, 1, D, sz, num);
elif (D[i] == ord(num[pos]) - ord('0')) :
val += calculate(pos + 1, tight, D, sz, num);
else :
# Loop to traverse all the
# digits from the given set
for i in range(sz) :
val += calculate(pos + 1, tight, D, sz, num);
# Store the solution for
# current subproblem
dp[pos][tight] = val;
return dp[pos][tight];
# Function to count the numbers
# less than N from given set of digits
def countNumbers(D, N, sz) :
# Converting the number to string
num = convertToString(N);
length = len(num);
# Initially no subproblem
# is solved till now
# dp = np.ones((15,2))*-1;
# Find the solution of all the
# number equal to the length of
# the given number N
ans = calculate(0, 0, D, sz, num);
# Loop to find the number less in
# in the length of the given number
for i in range(1,length) :
ans += calculate(i, 1, D, sz, num);
return ans;
# Driver Code
if __name__ == "__main__" :
sz = 3;
D = [ 1, 4, 9 ];
N = 10;
# Function Call
print(countNumbers(D, N, sz));
# This code is contributed by AnkitRai01
C#
// C# implementation to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
using System;
class GFG{
static int [,]dp = new int[15, 2];
// Function to convert integer
// into the String
static String convertToString(int num)
{
return String.Join("",num);
}
// Recursive function to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
static int calculate(int pos, int tight,
int []D, int sz, String num)
{
// Base case
if (pos == num.Length)
return 1;
// Condition when the subproblem
// is computed previously
if (dp[pos,tight] != -1)
return dp[pos,tight];
int val = 0;
// Condition when the number
// chosen till now is definitely
// smaller than the given number N
if (tight == 0) {
// Loop to traverse all the
// digits of the given set
for (int i = 0; i < sz; i++) {
if (D[i] < (num[pos] - '0')) {
val += calculate(pos + 1,
1, D, sz, num);
}
else if (D[i] == num[pos] - '0')
val += calculate(pos + 1,
tight, D, sz, num);
}
}
else {
// Loop to traverse all the
// digits from the given set
for (int i = 0; i < sz; i++) {
val += calculate(pos + 1,
tight, D, sz, num);
}
}
// Store the solution for
// current subproblem
return dp[pos,tight] = val;
}
// Function to count the numbers
// less than N from given set of digits
static int countNumbers(int []D, int N, int sz)
{
// Converting the number to String
String num = convertToString(N);
int len = num.Length;
// Initially no subproblem
// is solved till now
for (int i = 0; i < 15; i++)
for (int j = 0; j < 2; j++)
dp[i,j] = -1;
// Find the solution of all the
// number equal to the length of
// the given number N
int ans = calculate(0, 0, D, sz, num);
// Loop to find the number less in
// in the length of the given number
for (int i = 1; i < len; i++)
ans += calculate(i, 1, D, sz, num);
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int sz = 3;
int []D = { 1, 4, 9 };
int N = 10;
// Function Call
Console.Write(countNumbers(D, N, sz));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
var dp = Array.from(Array(15), ()=>Array(2).fill(-1));
// Recursive function to find the
// count of numbers possible less
// than N, such that every digit
// is from the given set of digits
function calculate(pos, tight, D, sz, num)
{
// Base case
if (pos == num.length)
return 1;
// Condition when the subproblem
// is computed previously
if (dp[pos][tight] != -1)
return dp[pos][tight];
var val = 0;
// Condition when the number
// chosen till now is definitely
// smaller than the given number N
if (tight == 0) {
// Loop to traverse all the
// digits of the given set
for (var i = 0; i < sz; i++) {
if (D[i] < (num[pos] - '0')) {
val += calculate(pos + 1,
1, D, sz, num);
}
else if (D[i] == num[pos] - '0')
val += calculate(pos + 1,
tight, D, sz, num);
}
}
else {
// Loop to traverse all the
// digits from the given set
for (var i = 0; i < sz; i++) {
val += calculate(pos + 1,
tight, D, sz, num);
}
}
// Store the solution for
// current subproblem
return dp[pos][tight] = val;
}
// Function to count the numbers
// less than N from given set of digits
function countNumbers(D, N, sz)
{
// Converting the number to string
var num = (N.toString());
var len = num.length;
// Find the solution of all the
// number equal to the length of
// the given number N
var ans = calculate(0, 0, D, sz, num);
// Loop to find the number less in
// in the length of the given number
for (var i = 1; i < len; i++)
ans += calculate(i, 1, D, sz, num);
return ans;
}
// Driver Code
var sz = 3;
var D = [1, 4, 9];
var N = 10;
// Function Call
document.write( countNumbers(D, N, sz));
</script>
Producción:
3
Complejidad de tiempo : O(Len(D))
Complejidad de espacio : O(12*2)