Dado un número N y una suma S, encuentre la cuenta de números hasta N que tienen una suma de dígitos igual a S.
Examples: Input : N = 100, S = 4 Output : 5 Upto 100 only 5 numbers(4, 13, 22, 31, 40) can produce 4 as their sum of digits. Input : N = 1000, S = 1 Output : 4 Upto 1000 only 4 numbers(1, 10, 100 and 1000) can produce 1 as their sum of digits.
Podemos hacer un dígito DP que tenga estado (índice actual, si el número de i dígitos actualmente construido es igual o menor que el número formado por los primeros i dígitos de N, la suma de los dígitos del número actualmente construido).
Sea dp[i][tight][sum_so_far] el conteo de números cuyos primeros i dígitos han sido considerados y tight denota si el número construido actualmente es igual o menor que el número formado por los primeros i dígitos de N. Si tight es verdadero, entonces significa que el número actualmente construido es igual al número construido por los primeros i dígitos de N. Si es falso, entonces significa que el número actualmente construido es menor que el número construido por los primeros i dígitos de N. sum_so_far denota la suma de dígitos del número actualmente construido.
Caso base:
si i = número de dígitos en N, sum_so_far = Sum, entonces la respuesta = 1, de lo contrario, la respuesta es 0.
Transiciones:
para llenar (i+1)th dígito, podemos considerar lo siguiente:
si tight es verdadero, significa que nuestro número construido sigue siendo igual al número formado por los primeros i dígitos de N. Podemos probar nuestro posible valor de dígito actual de 0 a (i+1)th dígito de N. Si probamos el dígito más que (i+1)th dígito, entonces el número construido será mayor que el número formado por los primeros i dígitos de N, lo que violará la propiedad de que nuestro número construido debe ser <= N.
Si tight es falso, entonces significa que el número construido a partir de los primeros i – 1 dígitos se ha vuelto menor que el número construido a partir del primer i – 1 dígito de N, por lo que significa que nuestro número nunca puede exceda N, por lo que podemos elegir cualquier dígito del 0 al 9.
nsum_so_far se puede obtener sumando sum_so_far y el dígito actual (currdigit).
Finalmente, devolveremos la respuesta, que es el conteo de números hasta N que tienen una suma de dígitos igual a S.
C++
#include <bits/stdc++.h>
using namespace std;
// N can be max 10^18 and hence digitsum will be 162 maximum.
long long dp[18][2][162];
long long solve(int i, bool tight, int sum_so_far,
int Sum, string number, int len)
{
if (i == len) {
// If sum_so_far equals to given sum then
// return 1 else 0
if (sum_so_far == Sum)
return 1;
else
return 0;
}
long long& ans = dp[i][tight][sum_so_far];
if (ans != -1) {
return ans;
}
ans = 0;
bool ntight;
int nsum_so_far;
for (char currdigit = '0'; currdigit <= '9'; currdigit++) {
// Our constructed number should not become
// greater than N.
if (!tight && currdigit > number[i]) {
break;
}
// If tight is true then it will also be true for (i+1) digit.
ntight = tight || currdigit < number[i];
nsum_so_far = sum_so_far + (currdigit - '0');
ans += solve(i + 1, ntight, nsum_so_far, Sum, number, len);
}
return ans;
}
// Driver code
int main()
{
long long count = 0;
long long sum = 4;
string number = "100";
memset(dp, -1, sizeof dp);
cout << solve(0, 0, 0, sum, number, number.size());
return 0;
}
Java
// Java program to count 2s from 0 to n
class GFG
{
// N can be max 10^18 and hence
// digitsum will be 162 maximum.
static long dp[][][] = new long[18][2][162];
static long solve(int i, boolean tight, int sum_so_far,
int Sum, String number, int len)
{
if (i == len)
{
// If sum_so_far equals to given sum then
// return 1 else 0
if (sum_so_far == Sum)
return 1;
else
return 0;
}
long ans = dp[i][1][sum_so_far];
if (ans != -1)
{
return ans;
}
ans = 0;
boolean ntight;
int nsum_so_far;
for (char currdigit = '0'; currdigit <= '9'; currdigit++)
{
// Our constructed number should not become
// greater than N.
if (!tight && currdigit > number.charAt(i))
{
break;
}
// If tight is true then it will
// also be true for (i+1) digit.
ntight = tight || currdigit < number.charAt(i);
nsum_so_far = sum_so_far + (currdigit - '0');
ans += solve(i + 1, ntight, nsum_so_far,
Sum, number, len);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
long count = 0;
int sum = 4;
String number = "100";
for(int i = 0; i < 18; i++)
{
for(int j = 0; j < 2; j++)
{
for(int k = 0; k < 162; k++)
dp[i][j][k] = -1;
}
}
System.out.println( solve(0, false, 0, sum,
number, number.length()));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the given approach. def solve(i, tight, sum_so_far, Sum, number, length): if i == length: # If sum_so_far equals to given # sum then return 1 else 0 if sum_so_far == Sum: return 1 else: return 0 ans = dp[i][tight][sum_so_far] if ans != -1: return ans ans = 0 for currdigit in range(0, 10): currdigitstr = str(currdigit) # Our constructed number should # not become greater than N. if not tight and currdigitstr > number[i]: break # If tight is true then it will also be true for (i+1) digit. ntight = tight or currdigitstr < number[i] nsum_so_far = sum_so_far + currdigit ans += solve(i + 1, ntight, nsum_so_far, Sum, number, length) return ans # Driver code if __name__ == "__main__": count, Sum = 0, 4 number = "100" dp = [[[-1 for i in range(162)] for j in range(2)] for k in range(18)] print(solve(0, 0, 0, Sum, number, len(number))) # This code is contributed by Rituraj Jain
C#
// C# program to count 2s from 0 to n
using System;
class GFG
{
// N can be max 10^18 and hence
// digitsum will be 162 maximum.
static long [ , , ]dp = new long[18,2,162];
static long solve(int i, bool tight, int sum_so_far,
int Sum, String number, int len)
{
if (i == len)
{
// If sum_so_far equals to given sum then
// return 1 else 0
if (sum_so_far == Sum)
return 1;
else
return 0;
}
long ans = dp[i,1,sum_so_far];
if (ans != -1)
{
return ans;
}
ans = 0;
bool ntight;
int nsum_so_far;
for (char currdigit = '0'; currdigit <= '9'; currdigit++)
{
// Our constructed number should not become
// greater than N.
if (!tight && currdigit > number[i])
{
break;
}
// If tight is true then it will
// also be true for (i+1) digit.
ntight = tight || currdigit < number[i];
nsum_so_far = sum_so_far + (currdigit - '0');
ans += solve(i + 1, ntight, nsum_so_far,
Sum, number, len);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int sum = 4;
String number = "100";
for(int i = 0; i < 18; i++)
{
for(int j = 0; j < 2; j++)
{
for(int k = 0; k < 162; k++)
dp[i,j,k] = -1;
}
}
Console.WriteLine( solve(0, false, 0, sum,
number, number.Length));
}
}
// This code has been contributed by Rajput-Ji
5
Complejidad de tiempo: 2 (ajustado) * Suma * log 10 (N) * 10 (transiciones) = 20 * log 10 (N) * Suma.
Publicación traducida automáticamente
Artículo escrito por Vishwanath Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA