Dados tres números enteros positivos L , R e Y , la tarea es contar los números en el rango [L, R] cuya suma de dígitos es igual a Y
Ejemplos:
Entrada: L = 500, R = 1000, Y = 6
Salida: 3
Explicación:
Los números en el rango [500, 600] cuya suma de dígitos es Y(= 6) son:
501 = 5 + 0 + 1 = 6
510 = 5 + 1 + 0 = 6
600 = 6 + 0 + 0 = 6
Por lo tanto, la salida requerida es 3.Entrada: L = 20, R = 10000, Y = 14
Salida: 540
Enfoque ingenuo: consulte la publicación anterior para resolver este problema iterando sobre todos los números en el rango [L, R] , y para cada número, verifique si su suma de dígitos es igual a Y o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
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 usando la siguiente relación de recurrencia:
donde, suma: Representa la suma de dígitos.
apretado: comprueba si la suma de los dígitos supera Y o no.
end: Almacena el valor máximo posible del i -ésimo dígito de un número.
cntNum(N, Y, tight): Devuelve el conteo de números en el rango [0, X] cuya suma de dígitos es Y.
Antes de pasar a la solución de DP, es una buena práctica anotar el código recursivo.
Aquí está el código recursivo:
C++
// C++ Program for the same approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of digits
// of numbers in the range [0, X]
int cntNum(string X, int i, int sum, int tight)
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.length() || sum < 0) {
// Check if sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Stores count of numbers whose
// sum of digits is Y
int res = 0;
// Check if the number
// exceeds Y or not
int end = tight != 0 ? X[i] - '0' : 9;
// Iterate over all possible
// values of i-th digits
for (int j = 0; j <= end; j++) {
// Update res
res += cntNum(X, i + 1, sum - j,
(tight > 0 & (j == end)) ==
true ? 1 : 0);
}
// Return res
return res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L,int R,int Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent String
string str = to_string(R);
// Stores count of numbers
// in the range [0, R]
int cntR = cntNum(str, 0, Y,
1);
// Update str
str = to_string(L - 1);
// Stores count of numbers in
// the range [0, L - 1]
int cntL = cntNum(str, 0, Y,
1);
return (cntR - cntL);
}
// Driver code
int main()
{
int L = 20, R = 10000, Y = 14;
cout<<(UtilCntNumRange(L, R, Y));
}
// This code is contributed by shinjanpatra
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(String X, int i, int sum,
int tight)
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.length() || sum < 0) {
// Check if sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Stores count of numbers whose
// sum of digits is Y
int res = 0;
// Check if the number
// exceeds Y or not
int end = tight != 0 ? X.charAt(i) - '0' : 9;
// Iterate over all possible
// values of i-th digits
for (int j = 0; j <= end; j++) {
// Update res
res += cntNum(X, i + 1, sum - j,
(tight > 0 & (j == end)) ==
true ? 1 : 0);
}
// Return res
return res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L,int R,int Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent String
String str = String.valueOf(R);
// Stores count of numbers
// in the range [0, R]
int cntR = cntNum(str, 0, Y,
1);
// Update str
str = String.valueOf(L - 1);
// Stores count of numbers in
// the range [0, L - 1]
int cntL = cntNum(str, 0, Y,
1);
return (cntR - cntL);
}
// Driver Code
public static void main (String[] args)
{
int L = 20, R = 10000, Y = 14;
System.out.print(UtilCntNumRange(L, R, Y));
}
}
// This code is contributed by Debojyoti Mandal
Python3
# Python program for the above approach
# Function to find the sum of digits
# of numbers in the range [0, X]
def cntNum(X, i, sum, tight):
# Check if count of digits in a number
# greater than count of digits in X
if (i >= len(X) or sum < 0):
# Check if sum of digits of a
# number is equal to Y
if (sum == 0):
return 1
return 0
# Stores count of numbers whose
# sum of digits is Y
res = 0
# Check if the number
# exceeds Y or not
end = ord(X[i]) - ord('0') if tight else 9
# Iterate over all possible
# values of i-th digits
for j in range(end+1):
# Update res
res += cntNum(X, i + 1, sum - j,1 if((tight > 0 and (j == end)) == True) else 0)
# Return res
return res
# Utility function to count the numbers in
# the range [L, R] whose sum of digits is Y
def UtilCntNumRange(L, R, Y):
# Base Case
if (R == 0 and Y == 0):
return 1
# Stores numbers in the form
# of its equivalent String
Str = str(R)
# Stores count of numbers
# in the range [0, R]
cntR = cntNum(Str, 0, Y,1)
# Update str
Str = str(L - 1)
# Stores count of numbers in
# the range [0, L - 1]
cntL = cntNum(Str, 0, Y, 1)
return (cntR - cntL)
# Driver Code
L, R, Y = 20, 10000, 14
print(UtilCntNumRange(L, R, Y))
# This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(string X, int i, int sum, int tight)
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.Length || sum < 0) {
// Check if sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Stores count of numbers whose
// sum of digits is Y
int res = 0;
// Check if the number
// exceeds Y or not
int end = tight != 0 ? X[i] - '0' : 9;
// Iterate over all possible
// values of i-th digits
for (int j = 0; j <= end; j++) {
// Update res
res += cntNum(
X, i + 1, sum - j,
(tight > 0 & (j == end)) == true ? 1 : 0);
}
// Return res
return res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L, int R, int Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent String
string str = R.ToString();
// Stores count of numbers
// in the range [0, R]
int cntR = cntNum(str, 0, Y, 1);
// Update str
str = (L - 1).ToString();
// Stores count of numbers in
// the range [0, L - 1]
int cntL = cntNum(str, 0, Y, 1);
return (cntR - cntL);
}
// Driver Code
public static void Main(string[] args)
{
int L = 20, R = 10000, Y = 14;
Console.WriteLine(UtilCntNumRange(L, R, Y));
}
}
// This code is contributed by ukasp.
Javascript
// JavaScript program for the above approach
// Function to find the sum of digits
// of numbers in the range [0, X]
function cntNum( X, i, sum, tight)
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.length || sum < 0) {
// Check if sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Stores count of numbers whose
// sum of digits is Y
var res = 0;
// Check if the number
// exceeds Y or not
var end = tight != 0 ? X[i].charCodeAt(0) - '0'.charCodeAt(0) : 9;
// Iterate over all possible
// values of i-th digits
for (var j = 0; j <= end; j++) {
// Update res
res += cntNum(X, i + 1, sum - j,
(tight > 0 & (j == end)) ==
true ? 1 : 0);
}
// Return res
return res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
function UtilCntNumRange(L, R, Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent String
var str = (R).toString();
// Stores count of numbers
// in the range [0, R]
var cntR = cntNum(str, 0, Y,
1);
// Update str
str = (L - 1).toString();
// Stores count of numbers in
// the range [0, L - 1]
var cntL = cntNum(str, 0, Y,
1);
return (cntR - cntL);
}
// Driver Code
var L = 20, R = 10000, Y = 14;
document.write(UtilCntNumRange(L, R, Y));
// This code is contributed by shivanisinghss2110
Producción
540
Siga los pasos a continuación para resolver el problema usando DP.
- Inicialice una array 3D dp[N][Y][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++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define M 1000
// Function to find the sum of digits
// of numbers in the range [0, X]
int cntNum(string X, int i, int sum,
int tight, int dp[M][M][2])
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.length() || sum < 0) {
// If sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Check if current subproblem has
// already been computed
if (dp[sum][i][tight] != -1) {
return dp[sum][i][tight];
}
// Stores count of numbers whose
// sum of digits is Y
int res = 0;
// Check if the number
// exceeds Y or not
int end = tight ? X[i] - '0' : 9;
// Iterate over all possible
// values of i-th digits
for (int j = 0; j <= end; j++) {
// Update res
res += cntNum(X, i + 1, sum - j,
(tight & (j == end)), dp);
}
// Return res
return dp[sum][i][tight]=res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
int UtilCntNumRange(int L, int R, int Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent string
string str = to_string(R);
// Stores overlapping subproblems
int dp[M][M][2];
// Initialize dp[][][]
memset(dp, -1, sizeof(dp));
// Stores count of numbers
// in the range [0, R]
int cntR = cntNum(str, 0, Y,
true, dp);
// Update str
str = to_string(L - 1);
// Initialize dp[][][]
memset(dp, -1, sizeof(dp));
// Stores count of numbers in
// the range [0, L - 1]
int cntL = cntNum(str, 0, Y,
true, dp);
return (cntR - cntL);
}
// Driver Code
int main()
{
int L = 20, R = 10000, Y = 14;
cout << UtilCntNumRange(L, R, Y);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int M = 1000;
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(String X, int i, int sum,
int tight, int dp[][][])
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.length() || sum < 0) {
// Check Iif sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Check if current subproblem has
// already been computed
if (dp[sum][i][tight] != -1) {
return dp[sum][i][tight];
}
// Stores count of numbers whose
// sum of digits is Y
int res = 0;
// Check if the number
// exceeds Y or not
int end = tight != 0 ? X.charAt(i) - '0' : 9;
// Iterate over all possible
// values of i-th digits
for (int j = 0; j <= end; j++) {
// Update res
res += cntNum(X, i + 1, sum - j,
(tight > 0 & (j == end)) ==
true ? 1 : 0, dp);
}
// Return res
return dp[sum][i][tight]=res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L, int R, int Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent String
String str = String.valueOf(R);
// Stores overlapping subproblems
int [][][]dp = new int[M][M][2];
// 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;
}
}
// Stores count of numbers
// in the range [0, R]
int cntR = cntNum(str, 0, Y,
1, dp);
// Update str
str = String.valueOf(L - 1);
// 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;
}
}
// Stores count of numbers in
// the range [0, L - 1]
int cntL = cntNum(str, 0, Y,
1, dp);
return (cntR - cntL);
}
// Driver Code
public static void main(String[] args)
{
int L = 20, R = 10000, Y = 14;
System.out.print(UtilCntNumRange(L, R, Y));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach
M = 1000
# Function to find the sum of digits
# of numbers in the range [0, X]
def cntNum(X, i, sum, tight, dp):
# Check if count of digits in a number
# greater than count of digits in X
if (i >= len(X) or sum < 0):
# Check if sum of digits of a
# number is equal to Y
if (sum == 0):
return 1
return 0
# Check if current subproblem has
# already been computed
if (dp[sum][i][tight] != -1):
return dp[sum][i][tight]
# Stores count of numbers whose
# sum of digits is Y
res, end = 0, 9
# Check if the number
# exceeds Y or not
if tight:
end = ord(X[i]) - ord('0')
# end = tight ? X[i] - '0' : 9;
# Iterate over all possible
# values of i-th digits
for j in range(end + 1):
# Update res
res += cntNum(X, i + 1, sum - j,
(tight & (j == end)), dp)
# Return res
dp[sum][i][tight] = res
return res
# Utility function to count the numbers in
# the range [L, R] whose sum of digits is Y
def UtilCntNumRange(L, R, Y):
# Base Case
if (R == 0 and Y == 0):
return 1
# Stores numbers in the form
# of its equivalent
strr = str(R)
# Stores overlapping subproblems
dp = [[[-1 for i in range(2)] for i in range(M)]
for i in range(M)]
# Initialize dp[][][]
# memset(dp, -1, sizeof(dp))
# Stores count of numbers
# in the range [0, R]
cntR = cntNum(strr, 0, Y, True, dp)
# Update str
strr = str(L - 1)
# Initialize dp[][][]
# memset(dp, -1, sizeof(dp))
# Stores count of numbers in
# the range [0, L - 1]
cntL = cntNum(strr, 0, Y, True, dp)
return (cntR - cntL)
# Driver Code
if __name__ == '__main__':
L, R, Y = 20, 10000, 14
print(UtilCntNumRange(L, R, Y))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
static readonly int M = 1000;
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(String X, int i, int sum,
int tight, int [,,]dp)
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.Length || sum < 0)
{
// Check if sum of digits of a
// number is equal to Y
if (sum == 0)
{
return 1;
}
return 0;
}
// Check if current subproblem has
// already been computed
if (dp[sum, i, tight] != -1)
{
return dp[sum, i, tight];
}
// Stores count of numbers whose
// sum of digits is Y
int res = 0;
// Check if the number
// exceeds Y or not
int end = tight != 0 ? X[i] - '0' : 9;
// Iterate over all possible
// values of i-th digits
for(int j = 0; j <= end; j++)
{
// Update res
res += cntNum(X, i + 1, sum - j,
(tight > 0 & (j == end)) ==
true ? 1 : 0, dp);
}
// Return res
return dp[sum][i][tight] = res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L, int R, int Y)
{
// Base Case
if (R == 0 && Y == 0)
{
return 1;
}
// Stores numbers in the form
// of its equivalent String
String str = String.Join("", R);
// Stores overlapping subproblems
int [,,]dp = new int[M, M, 2];
// 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;
}
}
// Stores count of numbers
// in the range [0, R]
int cntR = cntNum(str, 0, Y,
1, dp);
// Update str
str = String.Join("",L - 1);
// 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;
}
}
// Stores count of numbers in
// the range [0, L - 1]
int cntL = cntNum(str, 0, Y,
1, dp);
return (cntR - cntL);
}
// Driver Code
public static void Main(String[] args)
{
int L = 20, R = 10000, Y = 14;
Console.Write(UtilCntNumRange(L, R, Y));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let M = 1000;
// Function to find the sum of digits
// of numbers in the range [0, X]
function cntNum(X, i, sum, tight, dp)
{
// Check if count of digits in a number
// greater than count of digits in X
if (i >= X.length || sum < 0) {
// Check Iif sum of digits of a
// number is equal to Y
if (sum == 0) {
return 1;
}
return 0;
}
// Check if current subproblem has
// already been computed
if (dp[sum][i][tight] != -1) {
return dp[sum][i][tight];
}
// Stores count of numbers whose
// sum of digits is Y
let res = 0;
// Check if the number
// exceeds Y or not
let end = tight != 0 ? X[i].charCodeAt(0) - '0'.charCodeAt(0) : 9;
// Iterate over all possible
// values of i-th digits
for (let j = 0; j <= end; j++) {
// Update res
res += cntNum(X, i + 1, sum - j,
(tight > 0 & (j == end)) ==
true ? 1 : 0, dp);
}
// Return res
return dp[sum][i][tight]=res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
function UtilCntNumRange(L,R,Y)
{
// Base Case
if (R == 0 && Y == 0) {
return 1;
}
// Stores numbers in the form
// of its equivalent String
let str = (R).toString();
// Stores overlapping subproblems
let dp = new Array(M);
// Initialize dp[][][]
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] = -1;
}
}
// Stores count of numbers
// in the range [0, R]
let cntR = cntNum(str, 0, Y,
1, dp);
// Update str
str = (L - 1).toString();
// 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;
}
}
// Stores count of numbers in
// the range [0, L - 1]
let cntL = cntNum(str, 0, Y,
1, dp);
return (cntR - cntL);
}
// Driver Code
let L = 20, R = 10000, Y = 14;
document.write(UtilCntNumRange(L, R, Y));
// This code is contributed by patel2127
</script>
Producción
540
Complejidad de Tiempo: O(Y * log 10 (R) * 10)
Espacio Auxiliar: O(Y * log 10 (R)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA