Count N | C ++ program for the above approach ; Stores the value of overlapping states ; 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 ; 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 ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 1000 + 5 ] [ 9000 + 5 ] ; int mod = 1000000007 ; 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 ; } int countNumbers ( int n , int x , int y , int sum ) { memset ( dp , -1 , sizeof ( dp ) ) ; 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 ; } int main ( ) { int N = 3 , X = 1 , Y = 5 ; cout << countNumbers ( N , X , Y , 0 ) % mod ; }