Dados dos enteros ‘n’ y ‘suma’, encuentra el conteo de todos los números de n dígitos con suma de dígitos como ‘suma’. Los ceros iniciales no se cuentan como dígitos.
1 <= n <= 100 y
1 <= suma <= 500
Ejemplo:
Input: n = 2, sum = 2 Output: 2 Explanation: Numbers are 11 and 20 Input: n = 2, sum = 5 Output: 5 Explanation: Numbers are 14, 23, 32, 41 and 50 Input: n = 3, sum = 6 Output: 21
La idea es simple, restamos todos los valores de 0 a 9 de la suma dada y recurrimos a la suma menos ese dígito. A continuación se muestra la fórmula recursiva.
countRec(n, sum) = ∑countRec(n-1, sum-x)
where 0 =< x = 0
One important observation is, leading 0's must be
handled explicitly as they are not counted as digits.
So our final count can be written as below.
finalCount(n, sum) = ∑countRec(n-1, sum-x)
where 1 =< x = 0
A continuación se muestra una solución recursiva simple basada en la fórmula recursiva anterior.
C++
// A C++ program using recursive to count numbers
// with sum of digits as given 'sum'
#include<bits/stdc++.h>
using namespace std;
// Recursive function to count 'n' digit numbers
// with sum of digits as 'sum'. This function
// considers leading 0's also as digits, that is
// why not directly called
unsigned long long int countRec(int n, int sum)
{
// Base case
if (n == 0)
return sum == 0;
if (sum == 0)
return 1;
// Initialize answer
unsigned long long int ans = 0;
// Traverse through every digit and count
// numbers beginning with it using recursion
for (int i=0; i<=9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining digits.
unsigned long long int finalCount(int n, int sum)
{
// Initialize final answer
unsigned long long int ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for (int i = 1; i <= 9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
// Driver program
int main()
{
int n = 2, sum = 5;
cout << finalCount(n, sum);
return 0;
}
Java
// A Java program using recursive to count numbers
// with sum of digits as given 'sum'
class sum_dig
{
// Recursive function to count 'n' digit numbers
// with sum of digits as 'sum'. This function
// considers leading 0's also as digits, that is
// why not directly called
static int countRec(int n, int sum)
{
// Base case
if (n == 0)
return sum == 0 ?1:0;
if (sum == 0)
return 1;
// Initialize answer
int ans = 0;
// Traverse through every digit and count
// numbers beginning with it using recursion
for (int i=0; i<=9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining digits.
static int finalCount(int n, int sum)
{
// Initialize final answer
int ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for (int i = 1; i <= 9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
/* Driver program to test above function */
public static void main (String args[])
{
int n = 2, sum = 5;
System.out.println(finalCount(n, sum));
}
}/* This code is contributed by Rajat Mishra */
Python3
# A python 3 program using recursive to count numbers # with sum of digits as given 'sum' # Recursive function to count 'n' digit # numbers with sum of digits as 'sum' # This function considers leading 0's # also as digits, that is why not # directly called def countRec(n, sum) : # Base case if (n == 0) : return (sum == 0) if (sum == 0) : return 1 # Initialize answer ans = 0 # Traverse through every digit and # count numbers beginning with it # using recursion for i in range(0, 10) : if (sum-i >= 0) : ans = ans + countRec(n-1, sum-i) return ans # This is mainly a wrapper over countRec. It # explicitly handles leading digit and calls # countRec() for remaining digits. def finalCount(n, sum) : # Initialize final answer ans = 0 # Traverse through every digit from 1 to # 9 and count numbers beginning with it for i in range(1, 10) : if (sum-i >= 0) : ans = ans + countRec(n-1, sum-i) return ans # Driver program n = 2 sum = 5 print(finalCount(n, sum)) # This code is contributed by Nikita tiwari.
C#
// A C# program using recursive to count numbers
// with sum of digits as given 'sum'
using System;
class GFG {
// Recursive function to
// count 'n' digit numbers
// with sum of digits as
// 'sum'. This function
// considers leading 0's
// also as digits, that is
// why not directly called
static int countRec(int n, int sum)
{
// Base case
if (n == 0)
return sum == 0 ? 1 : 0;
if (sum == 0)
return 1;
// Initialize answer
int ans = 0;
// Traverse through every
// digit and count numbers
// beginning with it using
// recursion
for (int i = 0; i <= 9; i++)
if (sum - i >= 0)
ans += countRec(n - 1, sum - i);
return ans;
}
// This is mainly a
// wrapper over countRec. It
// explicitly handles leading
// digit and calls countRec()
// for remaining digits.
static int finalCount(int n, int sum)
{
// Initialize final answer
int ans = 0;
// Traverse through every
// digit from 1 to 9 and
// count numbers beginning
// with it
for (int i = 1; i <= 9; i++)
if (sum - i >= 0)
ans += countRec(n - 1, sum - i);
return ans;
}
// Driver Code
public static void Main ()
{
int n = 2, sum = 5;
Console.Write(finalCount(n, sum));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP program using recursive to count numbers
// with sum of digits as given 'sum'
// Recursive function to count 'n' digit numbers
// with sum of digits as 'sum'. This function
// considers leading 0's also as digits, that is
// why not directly called
function countRec($n, $sum)
{
// Base case
if ($n == 0)
return $sum == 0;
if ($sum == 0)
return 1;
// Initialize answer
$ans = 0;
// Traverse through every
// digit and count
// numbers beginning with
// it using recursion
for ($i = 0; $i <= 9; $i++)
if ($sum-$i >= 0)
$ans += countRec($n-1, $sum-$i);
return $ans;
}
// This is mainly a wrapper
// over countRec. It
// explicitly handles leading
// digit and calls
// countRec() for remaining digits.
function finalCount($n, $sum)
{
// Initialize final answer
$ans = 0;
// Traverse through every
// digit from 1 to
// 9 and count numbers
// beginning with it
for ($i = 1; $i <= 9; $i++)
if ($sum - $i >= 0)
$ans += countRec($n - 1, $sum - $i);
return $ans;
}
// Driver Code
$n = 2;
$sum = 5;
echo finalCount($n, $sum);
// This code is contributed by ajit
?>
Javascript
<script>
// A JavaScript program using
// recursive to count numbers
// with sum of digits as given 'sum'
// Recursive function to
// count 'n' digit numbers
// with sum of digits as 'sum'.
//This function
// considers leading 0's also as digits,
//that is why not directly called
function countRec(n, sum) {
// Base case
if (n == 0)
return sum == 0;
if (sum == 0)
return 1;
// Initialize answer
let ans = 0;
// Traverse through every
// digit and count
// numbers beginning with
// it using recursion
for (let i = 0; i <= 9; i++) {
if (sum - i >= 0)
ans += countRec(n - 1, sum - i);
}
return ans;
}
// This is mainly a wrapper over countRec.
// It explicitly handles leading digit
// and calls countRec() for remaining digits.
function finalCount(n, sum) {
// Initialize final answer
let ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for (let i = 1; i <= 9; i++) {
if (sum - i >= 0)
ans += countRec(n - 1, sum - i);
}
return ans;
}
// Driver program
let n = 2, sum = 5;
document.write(finalCount(n, sum));
//This code is contributed by Surbhi Tyagi
</script>
Producción:
5
La complejidad temporal de la solución anterior es exponencial. Si dibujamos el árbol de recursión completo, podemos observar que muchos subproblemas se resuelven una y otra vez. Por ejemplo, si comenzamos con n = 3 y suma = 10, podemos llegar a n = 1, suma = 8, considerando las secuencias de dígitos 1, 1 o 2, 0.
Dado que se vuelven a llamar los mismos subproblemas, este problema tiene subproblemas superpuestos propiedad. Entonces, el problema de suma cuadrada mínima tiene ambas propiedades (ver this y this ) de un problema de programación dinámica.
A continuación se muestra la implementación basada en Memoization.
C++
// A C++ memoization based recursive program to count
// numbers with sum of n as given 'sum'
#include<bits/stdc++.h>
using namespace std;
// A lookup table used for memoization
unsigned long long int lookup[101][501];
// Memoization based implementation of recursive
// function
unsigned long long int countRec(int n, int sum)
{
// Base case
if (n == 0)
return sum == 0;
// If this subproblem is already evaluated,
// return the evaluated value
if (lookup[n][sum] != -1)
return lookup[n][sum];
// Initialize answer
unsigned long long int ans = 0;
// Traverse through every digit and
// recursively count numbers beginning
// with it
for (int i=0; i<10; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return lookup[n][sum] = ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining n.
unsigned long long int finalCount(int n, int sum)
{
// Initialize all entries of lookup table
memset(lookup, -1, sizeof lookup);
// Initialize final answer
unsigned long long int ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for (int i = 1; i <= 9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
// Driver program
int main()
{
int n = 3, sum = 5;
cout << finalCount(n, sum);
return 0;
}
Java
// A Java memoization based recursive program to count
// numbers with sum of n as given 'sum'
class sum_dig
{
// A lookup table used for memoization
static int lookup[][] = new int[101][501];
// Memoization based implementation of recursive
// function
static int countRec(int n, int sum)
{
// Base case
if (n == 0)
return sum == 0 ? 1 : 0;
// If this subproblem is already evaluated,
// return the evaluated value
if (lookup[n][sum] != -1)
return lookup[n][sum];
// Initialize answer
int ans = 0;
// Traverse through every digit and
// recursively count numbers beginning
// with it
for (int i=0; i<10; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return lookup[n][sum] = ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining n.
static int finalCount(int n, int sum)
{
// Initialize all entries of lookup table
for(int i = 0; i <= 100; ++i){
for(int j = 0; j <= 500; ++j){
lookup[i][j] = -1;
}
}
// Initialize final answer
int ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for (int i = 1; i <= 9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
/* Driver program to test above function */
public static void main (String args[])
{
int n = 3, sum = 5;
System.out.println(finalCount(n, sum));
}
}/* This code is contributed by Rajat Mishra */
Python3
# A Python3 memoization based recursive # program to count numbers with Sum of n # as given 'Sum' # A lookup table used for memoization lookup = [[-1 for i in range(501)] for i in range(101)] # Memoization based implementation # of recursive function def countRec(n, Sum): # Base case if (n == 0): return Sum == 0 # If this subproblem is already evaluated, # return the evaluated value if (lookup[n][Sum] != -1): return lookup[n][Sum] # Initialize answer ans = 0 # Traverse through every digit and # recursively count numbers beginning # with it for i in range(10): if (Sum-i >= 0): ans += countRec(n - 1, Sum-i) lookup[n][Sum] = ans return lookup[n][Sum] # This is mainly a wrapper over countRec. It # explicitly handles leading digit and calls # countRec() for remaining n. def finalCount(n, Sum): # Initialize final answer ans = 0 # Traverse through every digit from 1 to # 9 and count numbers beginning with it for i in range(1, 10): if (Sum - i >= 0): ans += countRec(n - 1, Sum - i) return ans # Driver Code n, Sum = 3, 5 print(finalCount(n, Sum)) # This code is contributed by mohit kumar 29
C#
// A C# memoization based recursive program to count
// numbers with sum of n as given 'sum'
using System;
class sum_dig
{
// A lookup table used for memoization
static int [,]lookup = new int[101,501];
// Memoization based implementation of recursive
// function
static int countRec(int n, int sum)
{
// Base case
if (n == 0)
return sum == 0 ? 1 : 0;
// If this subproblem is already evaluated,
// return the evaluated value
if (lookup[n,sum] != -1)
return lookup[n,sum];
// Initialize answer
int ans = 0;
// Traverse through every digit and
// recursively count numbers beginning
// with it
for (int i=0; i<10; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return lookup[n,sum] = ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining n.
static int finalCount(int n, int sum)
{
// Initialize all entries of lookup table
for(int i = 0; i <= 100; ++i){
for(int j = 0; j <= 500; ++j){
lookup[i,j] = -1;
}
}
// Initialize final answer
int ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for (int i = 1; i <= 9; i++)
if (sum-i >= 0)
ans += countRec(n-1, sum-i);
return ans;
}
/* Driver program to test above function */
public static void Main ()
{
int n = 3, sum = 5;
Console.Write(finalCount(n, sum));
}
}
PHP
<?php
// A PHP memoization based recursive program
// to count numbers with sum of n as given 'sum'
// A lookup table used for memoization
$lookup = array_fill(0, 101,
array_fill(0, 501, -1));
// Memoization based implementation
// of recursive function
function countRec($n, $sum)
{
global $lookup;
// Base case
if ($n == 0)
return $sum == 0;
// If this subproblem is already evaluated,
// return the evaluated value
if ($lookup[$n][$sum] != -1)
return $lookup[$n][$sum];
// Initialize answer
$ans = 0;
// Traverse through every digit and
// recursively count numbers beginning
// with it
for ($i = 0; $i < 10; $i++)
if ($sum - $i >= 0)
$ans += countRec($n - 1, $sum - $i);
return $lookup[$n][$sum] = $ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining n.
function finalCount($n, $sum)
{
// Initialize all entries of lookup table
// Initialize final answer
$ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for ($i = 1; $i <= 9; $i++)
if ($sum-$i >= 0)
$ans += countRec($n - 1, $sum - $i);
return $ans;
}
// Driver Code
$n = 3;
$sum = 5;
echo finalCount($n, $sum);
// This code is contributed by mits
?>
Javascript
<script>
// A Javascript memoization based
// recursive program to count numbers
// with sum of n as given 'sum'
// A lookup table used for memoization
let lookup = new Array(101);
// Memoization based implementation
// of recursive function
function countRec(n, sum)
{
// Base case
if (n == 0)
return sum == 0 ? 1 : 0;
// If this subproblem is already evaluated,
// return the evaluated value
if (lookup[n][sum] != -1)
return lookup[n][sum];
// Initialize answer
let ans = 0;
// Traverse through every digit and
// recursively count numbers beginning
// with it
for(let i = 0; i < 10; i++)
if (sum - i >= 0)
ans += countRec(n - 1, sum - i);
return lookup[n][sum] = ans;
}
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining n.
function finalCount(n, sum)
{
// Initialize all entries of lookup table
for(let i = 0; i < 101; i++)
{
lookup[i] = new Array(501);
for(let j = 0; j < 501; j++)
{
lookup[i][j] = -1;
}
}
// Initialize final answer
let ans = 0;
// Traverse through every digit from 1 to
// 9 and count numbers beginning with it
for(let i = 1; i <= 9; i++)
if (sum - i >= 0)
ans += countRec(n - 1, sum - i);
return ans;
}
// Driver code
let n = 3, sum = 5;
document.write(finalCount(n, sum));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
15
Gracias a Gaurav Ahirwar por sugerir la solución anterior.
Otro método
Podemos contar fácilmente números de n dígitos cuya suma de dígitos es igual a la suma dada al iterar todos los n dígitos y verificar si la suma del número actual de n dígitos es igual a la suma dada, si es así, comenzaremos a incrementar el número en 9 hasta que alcance al número cuya suma de dígitos es mayor que la suma dada, entonces nuevamente incrementaremos en 1 hasta que encontremos otro número con la suma dada.
C++
// C++ program to Count of n digit numbers
// whose sum of digits equals to given sum
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
void findCount(int n, int sum) {
//in case n = 2 start is 10 and end is (100-1) = 99
int start = pow(10, n-1);
int end = pow(10, n)-1;
int count = 0;
int i = start;
while(i <= end) {
int cur = 0;
int temp = i;
while( temp != 0) {
cur += temp % 10;
temp = temp / 10;
}
if(cur == sum) {
count++;
i += 9;
}else
i++;
}
cout << count;
/* This code is contributed by Anshuman */
}
int main() {
int n = 3;
int sum = 5;
findCount(n,sum);
return 0;
}
Java
// Java program to Count of n digit numbers
// whose sum of digits equals to given sum
public class GFG {
public static void main(String[] args) {
int n = 3;
int sum = 5;
findCount(n,sum);
}
private static void findCount(int n, int sum) {
//in case n = 2 start is 10 and end is (100-1) = 99
int start = (int) Math.pow(10, n-1);
int end = (int) Math.pow(10, n)-1;
int count = 0;
int i = start;
while(i < end) {
int cur = 0;
int temp = i;
while( temp != 0) {
cur += temp % 10;
temp = temp / 10;
}
if(cur == sum) {
count++;
i += 9;
}else
i++;
}
System.out.println(count);
/* This code is contributed by Anshuman */
}
}
Python3
# Python3 program to Count of n digit numbers # whose sum of digits equals to given sum import math def findCount(n, sum): # in case n = 2 start is 10 and # end is (100-1) = 99 start = math.pow(10, n - 1); end = math.pow(10, n) - 1; count = 0; i = start; while(i <= end): cur = 0; temp = i; while(temp != 0): cur += temp % 10; temp = temp // 10; if(cur == sum): count = count + 1; i += 9; else: i = i + 1; print(count); # Driver Code n = 3; sum = 5; findCount(n, sum); # This code is contributed # by Akanksha Rai
C#
// C# program to Count of n digit numbers
// whose sum of digits equals to given sum
using System;
class GFG
{
private static void findCount(int n,
int sum)
{
// in case n = 2 start is 10 and
// end is (100-1) = 99
int start = (int) Math.Pow(10, n - 1);
int end = (int) Math.Pow(10, n) - 1;
int count = 0;
int i = start;
while(i < end)
{
int cur = 0;
int temp = i;
while( temp != 0)
{
cur += temp % 10;
temp = temp / 10;
}
if(cur == sum)
{
count++;
i += 9;
}
else
i++;
}
Console.WriteLine(count);
}
// Driver Code
public static void Main()
{
int n = 3;
int sum = 5;
findCount(n,sum);
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to Count of n digit numbers
// whose sum of digits equals to given sum
function findCount($n, $sum)
{
// In case n = 2 start is 10 and
// end is (100-1) = 99
$start = (int)pow(10, $n - 1);
$end = (int)pow(10, $n) - 1;
$count = 0;
$i = $start;
while($i < $end)
{
$cur = 0;
$temp = $i;
while( $temp != 0)
{
$cur += $temp % 10;
$temp = (int) $temp / 10;
}
if($cur == $sum)
{
$count++;
$i += 9;
}
else
$i++;
}
echo ($count);
}
// Driver Code
$n = 3;
$sum = 5;
findCount($n,$sum);
// This code is contributed
// by jit_t
?>
Javascript
<script>
// Javascript program to Count of n digit numbers
// whose sum of digits equals to given sum
function findCount(n, sum) {
// in case n = 2 start is 10 and end is (100-1) = 99
let start = Math.pow(10, n-1);
let end = Math.pow(10, n)-1;
let count = 0;
let i = start;
while(i <= end)
{
let cur = 0;
let temp = i;
while( temp != 0)
{
cur += temp % 10;
temp = parseInt(temp / 10);
}
if(cur == sum)
{
count++;
i += 9;
}else
i++;
}
document.write(count);
}
let n = 3;
let sum = 5;
findCount(n,sum);
// This code is contributed by souravmahato348.
</script>
Producción:
15
Complejidad de tiempo: O (suma)
Complejidad de espacio: O (1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA