Hello Everyone,
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.
// 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;
}
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.
Below is Memoization based the implementation.
// 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;
}
Output:
15
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++ 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;
}
Output:
15
Time Complexity: O(sum)
Space Complexity: O(1)