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>
Producción:
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>
Producción:
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