Count of n digit numbers whose sum of digits equals to given sum - GeeksforGeeks
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
Read full article from Count of n digit numbers whose sum of digits equals to given sum - GeeksforGeeks
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
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 <= 9and
sum-x >= 0
// 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; // 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;}// 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; // 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;}