Count of N | C ++ Program to implement the above approach ; Function to find maximum between two numbers ; Function to find minimum between two numbers ; Function to return the count of such numbers ; For 1 - digit numbers , the count is 10 irrespective of K ; dp [ j ] stores the number of such i - digit numbers ending with j ; Stores the results of length i ; Initialize count for 1 - digit numbers ; Compute values for count of digits greater than 1 ; Find the range of allowed numbers if last digit is j ; Perform Range update ; Prefix sum to find actual count of i - digit numbers ending with j ; Update dp [ ] ; Stores the final answer ; Return the final answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int max ( int num1 , int num2 ) { return ( num1 > num2 ) ? num1 : num2 ; } int min ( int num1 , int num2 ) { return ( num1 > num2 ) ? num2 : num1 ; } int getCount ( int n , int k ) { if ( n == 1 ) return 10 ; int dp [ 11 ] = { 0 } ; int next [ 11 ] = { 0 } ; for ( int i = 1 ; i <= 9 ; i ++ ) dp [ i ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= 9 ; j ++ ) { int l = max ( 0 , ( j - k ) ) ; int r = min ( 9 , ( j + k ) ) ; next [ l ] += dp [ j ] ; next [ r + 1 ] -= dp [ j ] ; } for ( int j = 1 ; j <= 9 ; j ++ ) next [ j ] += next [ j - 1 ] ; for ( int j = 0 ; j < 10 ; j ++ ) { dp [ j ] = next [ j ] ; next [ j ] = 0 ; } } int count = 0 ; for ( int i = 0 ; i <= 9 ; i ++ ) count += dp [ i ] ; return count ; } int main ( ) { int n = 2 , k = 1 ; cout << getCount ( n , k ) ; return 0 ; }