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 <= 50000
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 <= 9 and
sum-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 <= 9 and
sum-x >= 0
[ad type=”banner”]
Below is a simple recursive solution based on above recursive formula.
Java
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;
// 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));
}
}
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 of a dynamic programming problem.
[ad type=”banner”]
Below is Memoization based the implementation.
Java
class sum_dig
{
// A lookup table used for memoization
static int lookup[][] = new int[101][50001];
// Memoizatiob 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<=50000;++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 = 2, sum = 5;
System.out.println(finalCount(n, sum));
}
}
Output:
5
[ad type=”banner”]