Count of N | C ++ implementation of the approach ; Function to return the count of n - digit numbers that satisfy the given conditions ; DP array to store the pre - caluclated states ; Base cases ; i - digit numbers ending with 0 can be formed by concatenating 0 in the end of all the ( i - 1 ) - digit number ending at a non - zero digit ; i - digit numbers ending with non - zero can be formed by concatenating any non - zero digit in the end of all the ( i - 1 ) - digit number ending with any digit ; n - digit number ending with and ending with non - zero ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count_numbers ( int k , int n ) { int dp [ n + 1 ] [ 2 ] ; dp [ 1 ] [ 0 ] = 0 ; dp [ 1 ] [ 1 ] = k - 1 ; for ( int i = 2 ; i <= n ; i ++ ) { dp [ i ] [ 0 ] = dp [ i - 1 ] [ 1 ] ; dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] ) * ( k - 1 ) ; } return dp [ n ] [ 0 ] + dp [ n ] [ 1 ] ; } int main ( ) { int k = 10 ; int n = 3 ; cout << count_numbers ( k , n ) ; return 0 ; }