Given two integers ‘n’ and ‘sum’, find count of all n digit numbers with sum of digits as ‘sum’. Leading 0’s are not counted as digits.
Constrains:
1 <= n <= 100 and
1 <= sum <= 500
Example:
Input: n = 2, sum = 2
Output: 2
Explanation: Numbers are 11 and 20Input: n = 2, sum = 5
Output: 5
Explanation: Numbers are 14, 23, 32, 41 and 50Input: n = 3, sum = 6
Output: 21
Naive approach:
The idea is simple, we subtract all values from 0 to 9 from given sum and recur for sum minus that digit. Below is recursive formula.
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
Below is a simple recursive solution based on above recursive formula.
C++
// A C++ program using recursion 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 calledunsigned 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 programint main(){ int n = 2, sum = 5; cout << finalCount(n, sum); return 0;} |
Java
// A Java program using recursion to count numbers // with sum of digits as given 'sum'import java.io.*;public 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 recursion 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 calleddef 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 programn = 2sum = 5print(finalCount(n, sum))# This code is contributed by Nikita tiwari. |
C#
// A C# program using recursion 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. |
Javascript
<script>// A JavaScript program using // recursion 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> |
PHP
<?php// A PHP program using recursion 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 calledfunction 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?> |
Output
5
Time Complexity: O(2n)
Auxiliary Space: O(n)
Approach using 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 memoizationunsigned long long int lookup[101][501];// Memoization based implementation of recursive// functionunsigned 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 programint 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'import java.io.*;public 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 memoizationlookup = [[-1 for i in range(501)] for i in range(101)]# Memoization based implementation# of recursive functiondef 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 Coden, Sum = 3, 5print(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)); }} |
Javascript
<script>// A Javascript memoization based// recursive program to count numbers// with sum of n as given 'sum' // A lookup table used for memoizationlet lookup = new Array(101);// Memoization based implementation// of recursive functionfunction 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 codelet n = 3, sum = 5;document.write(finalCount(n, sum));// This code is contributed by avanitrachhadiya2155</script> |
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 functionfunction 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?> |
Output
15
Time Complexity: O(n*sum)
Auxiliary Space: O(101*501)
Another Method: We can easily count n digit numbers whose sum of digit equals to given sum by iterating all n digits and checking if current n digit number’s sum is equal to given sum, if it is then we will start increment number by 9 until it reaches to number whose sum of digit’s is greater than given sum, then again we will increment by 1 until we found another number with given sum.
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 sumimport java.io.*;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 mathdef 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 Coden = 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 sumusing 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 Codepublic static void Main() { int n = 3; int sum = 5; findCount(n,sum);}}// This code is contributed // by Akanksha Rai |
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> |
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?> |
Output
15
Time Complexity: O(log n)
Auxiliary Space: O(1)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
