Count N | C # program for the above approach ; Stores the value of overlapping states ; Function to find the count of numbers that are formed by digits X and Y and whose sum of digit also have digit X or Y ; Initialize dp array ; Base Case ; Check if sum of digits formed by only X or Y ; Return the already computed ; Place the digit X at the current position ; Place the digit Y at the current position ; Update current state result ; Function to check whether a number have only digits X or Y or not ; Until sum is positive ; If any digit is not X or Y then return 0 ; Return 1 ; Driver Code ; Function Call
using System ; class GFG { static int [ , ] dp = new int [ 100 + 5 , 900 + 5 ] ; static int mod = 10000007 ; public static int countNumbers ( int n , int x , int y , int sum ) { for ( int i = 0 ; i < dp . GetLength ( 0 ) ; i ++ ) { for ( int j = 0 ; j < dp . GetLength ( 1 ) ; j ++ ) { dp [ i , j ] = - 1 ; } } if ( n == 0 ) { return check ( sum , x , y ) ; } if ( dp [ n , sum ] != - 1 ) { return dp [ n , sum ] % mod ; } int option1 = countNumbers ( n - 1 , x , y , sum + x ) % mod ; int option2 = countNumbers ( n - 1 , x , y , sum + y ) % mod ; return dp [ n , sum ] = ( option1 + option2 ) % mod ; } public static int check ( int sum , int x , int y ) { while ( sum > 0 ) { int ln = sum % 10 ; if ( ln != x && ln != y ) { return 0 ; } sum /= 10 ; } return 1 ; } public static void Main ( String [ ] args ) { int N = 3 , X = 1 , Y = 5 ; Console . WriteLine ( countNumbers ( N , X , Y , 0 ) % mod ) ; } }