# Count of n digit numbers whose sum of digits equals to given sum

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.
1 <= n <= 100 and
1 <= sum <= 500

Example:

```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
```

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 recursive to count numbers  ` `// with sum of digits as given 'sum' ` `#include ` `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 */`

## Python 3

 `# 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

 `= 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`

The time complexity of above solution is exponential. If we draw the complete recursion tree, we can observer that many subproblems are solved again and again. For example, if we start with n = 3 and sum = 10, we can reach n = 1, sum = 8, by considering digit sequences 1,1 or 2, 0.
Since same suproblems are called again, this problem has Overlapping Subprolems property. So min square sum problem has both properties (see this and this) of a dynamic programming problem.

Below is Memoization based the implementation.

## C++

 `// A C++ memoization based recursive program to count  ` `// numbers with sum of n as given 'sum' ` `#include ` `using` `namespace` `std; ` ` `  `// A lookup table used for memoization ` `unsigned ``long` `long` `int` `lookup; ` ` `  `// 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

 `= 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`

Thanks to Gaurav Ahirwar for suggesting above solution.

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 ` `#include ` `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 [tabby title="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

 ` `

Output:

`15`

Time Complexity: O(sum)
Space Complexity: O(1)