Dados tres números enteros positivos L , R y K , la tarea es contar los números en el rango [L, R] cuyo producto de dígitos es igual a K
Ejemplos:
Entrada: L = 1, R = 130, K = 14
Salida: 3
Explicación:
Los números en el rango [1, 100] cuya suma de dígitos es K(= 14) son:
27 => 2 * 7 = 14
72 => 7 * 2 = 14
127 => 1 * 2 * 7 = 14
Por lo tanto, la salida requerida es 3.Entrada: L = 20, R = 10000, K = 14
Salida: 20
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre todos los números en el rango [L, R] y para cada número, verificar si su producto de dígitos es igual a K o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the product // of digits of a number int prodOfDigit(int N) { // Stores product of // digits of N int res = 1; while (N) { // Update res res = res * (N % 10); // Update N N /= 10; } return res; } // Function to count numbers in the range // [0, X] whose product of digit is K int cntNumRange(int L, int R, int K) { // Stores count of numbers in the range // [L, R] whose product of digit is K int cnt = 0; // Iterate over the range [L, R] for (int i = L; i <= R; i++) { // If product of digits of // i equal to K if (prodOfDigit(i) == K) { // Update cnt cnt++; } } return cnt; } // Driver Code int main() { int L = 20, R = 10000, K = 14; cout << cntNumRange(L, R, K); }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the product // of digits of a number static int prodOfDigit(int N) { // Stores product of // digits of N int res = 1; while (N > 0) { // Update res res = res * (N % 10); // Update N N /= 10; } return res; } // Function to count numbers in the range // [0, X] whose product of digit is K static int cntNumRange(int L, int R, int K) { // Stores count of numbers in the range // [L, R] whose product of digit is K int cnt = 0; // Iterate over the range [L, R] for (int i = L; i <= R; i++) { // If product of digits of // i equal to K if (prodOfDigit(i) == K) { // Update cnt cnt++; } } return cnt; } // Driver Code public static void main(String[] args) { int L = 20, R = 10000, K = 14; System.out.print(cntNumRange(L, R, K)); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach # Function to find the product # of digits of a number def prodOfDigit(N): # Stores product of # digits of N res = 1 while (N): # Update res res = res * (N % 10) # Update N N //= 10 return res # Function to count numbers in the range # [0, X] whose product of digit is K def cntNumRange(L, R, K): # Stores count of numbers in the range # [L, R] whose product of digit is K cnt = 0 # Iterate over the range [L, R] for i in range(L, R + 1): # If product of digits of # i equal to K if (prodOfDigit(i) == K): # Update cnt cnt += 1 return cnt # Driver Code if __name__ == '__main__': L, R, K = 20, 10000, 14 print(cntNumRange(L, R, K)) # This code is contributed by mohit kumar 29
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the product // of digits of a number static int prodOfDigit(int N) { // Stores product of // digits of N int res = 1; while (N > 0) { // Update res res = res * (N % 10); // Update N N /= 10; } return res; } // Function to count numbers in the range // [0, X] whose product of digit is K static int cntNumRange(int L, int R, int K) { // Stores count of numbers in the range // [L, R] whose product of digit is K int cnt = 0; // Iterate over the range [L, R] for(int i = L; i <= R; i++) { // If product of digits of // i equal to K if (prodOfDigit(i) == K) { // Update cnt cnt++; } } return cnt; } // Driver Code static void Main() { int L = 20, R = 10000, K = 14; Console.WriteLine(cntNumRange(L, R, K)); } } // This code is contributed by code_hunt
Javascript
<script> // Javascript program to implement // the above approach // Function to find the product // of digits of a number function prodOfDigit(N) { // Stores product of // digits of N let res = 1; while (N) { // Update res res = res * (N % 10); // Update N N = Math.floor(N/10); } return res; } // Function to count numbers in the range // [0, X] whose product of digit is K function cntNumRange(L, R, K) { // Stores count of numbers in the range // [L, R] whose product of digit is K let cnt = 0; // Iterate over the range [L, R] for (let i = L; i <= R; i++) { // If product of digits of // i equal to K if (prodOfDigit(i) == K) { // Update cnt cnt++; } } return cnt; } // Driver Code let L = 20, R = 10000, K = 14; document.write(cntNumRange(L, R, K)); // This code is contributed by manoj. </script>
20
Complejidad de tiempo: O(R – L + 1) * log 10 (R)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Digit DP . Los siguientes son los estados de programación dinámica del Digit DP:
Los estados de programación dinámica son:
prod: Representa la suma de dígitos.
apretado: comprueba si la suma de los dígitos supera a K o no.
end: Almacena el valor máximo posible del i -ésimo dígito de un número.
st: Comprueba si un número contiene un 0 inicial o no.
Las siguientes son las relaciones de recurrencia de los estados de programación dinámica:
- Si i == 0 y st == 0:
cntNum(N, K, st, tight): Devuelve el conteo de números en el rango [0, X] cuyo producto de dígitos es K.
- De lo contrario,
cntNum(N, K, st, tight): Devuelve el conteo de números en el rango [0, X] cuyo producto de dígitos es K.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 3D dp[N][K][tight] para calcular y almacenar los valores de todos los subproblemas de la relación de recurrencia anterior.
- Finalmente, devuelve el valor de dp[N][sum][tight] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define M 100 // Function to count numbers in the range // [0, X] whose product of digit is K int cntNum(string X, int i, int prod, int K, int st, int tight, int dp[M][M][2][2]) { // If count of digits in a number // greater than count of digits in X if (i >= X.length() || prod > K) { // If product of digits of a // number equal to K return prod == K; } // If overlapping subproblems // already occurred if (dp[prod][i][tight][st] != -1) { return dp[prod][i][tight][st]; } // Stores count of numbers whose // product of digits is K int res = 0; // Check if the numbers // exceeds K or not int end = tight ? X[i] - '0' : 9; // Iterate over all possible // value of i-th digits for (int j = 0; j <= end; j++) { // if number contains leading 0 if (j == 0 && !st) { // Update res res += cntNum(X, i + 1, prod, K, false, (tight & (j == end)), dp); } else { // Update res res += cntNum(X, i + 1, prod * j, K, true, (tight & (j == end)), dp); } // Update res } // Return res return dp[prod][i][tight][st] = res; } // Utility function to count the numbers in // the range [L, R] whose prod of digits is K int UtilCntNumRange(int L, int R, int K) { // Stores numbers in the form // of string string str = to_string(R); // Stores overlapping subproblems int dp[M][M][2][2]; // Initialize dp[][][] to -1 memset(dp, -1, sizeof(dp)); // Stores count of numbers in // the range [0, R] whose // product of digits is k int cntR = cntNum(str, 0, 1, K, false, true, dp); // Update str str = to_string(L - 1); // Initialize dp[][][] to -1 memset(dp, -1, sizeof(dp)); // Stores count of numbers in // the range [0, L - 1] whose // product of digits is k int cntL = cntNum(str, 0, 1, K, false, true, dp); return (cntR - cntL); } // Driver Code int main() { int L = 20, R = 10000, K = 14; cout << UtilCntNumRange(L, R, K); }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ static final int M = 100; // Function to count numbers in the range // [0, X] whose product of digit is K static int cntNum(String X, int i, int prod, int K, int st, int tight, int [][][][]dp) { // If count of digits in a number // greater than count of digits in X if (i >= X.length() || prod > K) { // If product of digits of a // number equal to K return prod == K ? 1 : 0; } // If overlapping subproblems // already occurred if (dp[prod][i][tight][st] != -1) { return dp[prod][i][tight][st]; } // Stores count of numbers whose // product of digits is K int res = 0; // Check if the numbers // exceeds K or not int end = tight > 0 ? X.charAt(i) - '0' : 9; // Iterate over all possible // value of i-th digits for(int j = 0; j <= end; j++) { // If number contains leading 0 if (j == 0 && st == 0) { // Update res res += cntNum(X, i + 1, prod, K, 0, (tight & ((j == end) ? 1 : 0)), dp); } else { // Update res res += cntNum(X, i + 1, prod * j, K, 1, (tight & ((j == end) ? 1 : 0)), dp); } } // Return res return dp[prod][i][tight][st] = res; } // Utility function to count the numbers in // the range [L, R] whose prod of digits is K static int UtilCntNumRange(int L, int R, int K) { // Stores numbers in the form // of String String str = String.valueOf(R); // Stores overlapping subproblems int [][][][]dp = new int[M][M][2][2]; // Initialize dp[][][] to -1 for(int i = 0; i < M; i++) { for(int j = 0; j < M; j++) { for(int k = 0; k < 2; k++) for(int l = 0; l < 2; l++) dp[i][j][k][l] = -1; } } // Stores count of numbers in // the range [0, R] whose // product of digits is k int cntR = cntNum(str, 0, 1, K, 0, 1, dp); // Update str str = String.valueOf(L - 1); // Initialize dp[][][] to -1 for(int i = 0;i<M;i++) { for(int j = 0; j < M; j++) { for(int k = 0; k < 2; k++) for(int l = 0; l < 2; l++) dp[i][j][k][l] = -1; } } // Stores count of numbers in // the range [0, L - 1] whose // product of digits is k int cntL = cntNum(str, 0, 1, K, 0, 1, dp); return (cntR - cntL); } // Driver Code public static void main(String[] args) { int L = 20, R = 10000, K = 14; System.out.print(UtilCntNumRange(L, R, K)); } } // This code is contributed by shikhasingrajput
Python3
# Python 3 program to implement # the above approach M = 100 # Function to count numbers in the range # [0, X] whose product of digit is K def cntNum(X, i, prod, K, st, tight, dp): end = 0 # If count of digits in a number # greater than count of digits in X if (i >= len(X) or prod > K): # If product of digits of a # number equal to K if(prod == K): return 1 else: return 0 # If overlapping subproblems # already occurred if (dp[prod][i][tight][st] != -1): return dp[prod][i][tight][st] # Stores count of numbers whose # product of digits is K res = 0 # Check if the numbers # exceeds K or not if(tight != 0): end = ord(X[i]) - ord('0') # Iterate over all possible # value of i-th digits for j in range(end + 1): # if number contains leading 0 if (j == 0 and st == 0): # Update res res += cntNum(X, i + 1, prod, K, False, (tight & (j == end)), dp) else: # Update res res += cntNum(X, i + 1, prod * j, K, True, (tight & (j == end)), dp) # Update res # Return res dp[prod][i][tight][st] = res return res # Utility function to count the numbers in # the range [L, R] whose prod of digits is K def UtilCntNumRange(L, R, K): global M # Stores numbers in the form # of string str1 = str(R) # Stores overlapping subproblems dp = [[[[-1 for i in range(2)] for j in range(2)] for k in range(M)] for l in range(M)] # Stores count of numbers in # the range [0, R] whose # product of digits is k cntR = cntNum(str1, 0, 1, K, False, True, dp) # Update str str1 = str(L - 1) dp = [[[[-1 for i in range(2)] for j in range(2)] for k in range(M)] for l in range(M)] # Stores count of numbers in cntR = 20 # the range [0, L - 1] whose # product of digits is k cntL = cntNum(str1, 0, 1, K, False, True, dp) return (cntR - cntL) # Driver Code if __name__ == '__main__': L = 20 R = 10000 K = 14 print(UtilCntNumRange(L, R, K)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program to implement // the above approach using System; class GFG { static readonly int M = 100; // Function to count numbers in the range // [0, X] whose product of digit is K static int cntNum(String X, int i, int prod, int K, int st, int tight, int [,,,]dp) { // If count of digits in a number // greater than count of digits in X if (i >= X.Length || prod > K) { // If product of digits of a // number equal to K return prod == K ? 1 : 0; } // If overlapping subproblems // already occurred if (dp[prod, i, tight, st] != -1) { return dp[prod, i, tight, st]; } // Stores count of numbers whose // product of digits is K int res = 0; // Check if the numbers // exceeds K or not int end = tight > 0 ? X[i] - '0' : 9; // Iterate over all possible // value of i-th digits for(int j = 0; j <= end; j++) { // If number contains leading 0 if (j == 0 && st == 0) { // Update res res += cntNum(X, i + 1, prod, K, 0, (tight & ((j == end) ? 1 : 0)), dp); } else { // Update res res += cntNum(X, i + 1, prod * j, K, 1, (tight & ((j == end) ? 1 : 0)), dp); } } // Return res return dp[prod, i, tight, st] = res; } // Utility function to count the numbers in // the range [L, R] whose prod of digits is K static int UtilCntNumRange(int L, int R, int K) { // Stores numbers in the form // of String String str = String.Join("", R); // Stores overlapping subproblems int [,,,]dp = new int[M, M, 2, 2]; // Initialize [,]dp[] to -1 for(int i = 0; i < M; i++) { for(int j = 0; j < M; j++) { for(int k = 0; k < 2; k++) for(int l = 0; l < 2; l++) dp[i, j, k, l] = -1; } } // Stores count of numbers in // the range [0, R] whose // product of digits is k int cntR = cntNum(str, 0, 1, K, 0, 1, dp); // Update str str = String.Join("", L - 1); // Initialize [,]dp[] to -1 for(int i = 0; i < M; i++) { for(int j = 0; j < M; j++) { for(int k = 0; k < 2; k++) for(int l = 0; l < 2; l++) dp[i, j, k, l] = -1; } } // Stores count of numbers in // the range [0, L - 1] whose // product of digits is k int cntL = cntNum(str, 0, 1, K, 0, 1, dp); return (cntR - cntL); } // Driver Code public static void Main(String[] args) { int L = 20, R = 10000, K = 14; Console.Write(UtilCntNumRange(L, R, K)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program to implement // the above approach let M = 100; // Function to count numbers in the range // [0, X] whose product of digit is K function cntNum(X, i, prod, K, st, tight, dp) { // If count of digits in a number // greater than count of digits in X if (i >= X.length || prod > K) { // If product of digits of a // number equal to K return prod == K ? 1 : 0; } // If overlapping subproblems // already occurred if (dp[prod][i][tight][st] != -1) { return dp[prod][i][tight][st]; } // Stores count of numbers whose // product of digits is K let res = 0; // Check if the numbers // exceeds K or not let end = tight > 0 ? X[i] - '0' : 9; // Iterate over all possible // value of i-th digits for(let j = 0; j <= end; j++) { // If number contains leading 0 if (j == 0 && st == 0) { // Update res res += cntNum(X, i + 1, prod, K, 0, (tight & ((j == end) ? 1 : 0)), dp); } else { // Update res res += cntNum(X, i + 1, prod * j, K, 1, (tight & ((j == end) ? 1 : 0)), dp); } } // Return res return dp[prod][i][tight][st] = res; } // Utility function to count the numbers in // the range [L, R] whose prod of digits is K function UtilCntNumRange(L,R,K) { // Stores numbers in the form // of String let str = (R).toString(); // Stores overlapping subproblems let dp = new Array(M); // Initialize dp[][][] to -1 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]=new Array(2); for(let l = 0; l < 2; l++) dp[i][j][k][l] = -1; } } } // Stores count of numbers in // the range [0, R] whose // product of digits is k let cntR = cntNum(str, 0, 1, K, 0, 1, dp); // Update str str = (L - 1).toString(); // Initialize dp[][][] to -1 for(let i = 0;i<M;i++) { for(let j = 0; j < M; j++) { for(let k = 0; k < 2; k++) for(let l = 0; l < 2; l++) dp[i][j][k][l] = -1; } } // Stores count of numbers in // the range [0, L - 1] whose // product of digits is k let cntL = cntNum(str, 0, 1, K, 0, 1, dp); return (cntR - cntL); } // Driver Code let L = 20, R = 10000, K = 14; document.write(UtilCntNumRange(L, R, K)); // This code is contributed by unknown2108 </script>
20
Complejidad de Tiempo: O(K * log 10 (R) * 10 * 4)
Espacio Auxiliar: O(K * log 10 (R) * 4)
Publicación traducida automáticamente
Artículo escrito por deepanshujindal634 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA