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
using System ; class GFG { static int count_numbers ( int k , int n ) { int [ , ] dp = new int [ 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 ] ; } public static void Main ( String [ ] args ) { int k = 10 ; int n = 3 ; Console . WriteLine ( count_numbers ( k , n ) ) ; } }