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>
3
Complejidad de tiempo : O(Len(D))
Complejidad de espacio : O(12*2)