Find the numbers from 1 to N that contains exactly k non | C # implementation of the above approach ; Function to find number less than N having k non - zero digits ; Store the memorised values ; Initialise ; Base ; Calculate all states For every state , from numbers 1 to N , the count of numbers which contain exactly j non zero digits is being computed and updated in the dp array . ; Return the required answer ; Driver code ; Function call
using System ; using System . Collections ; class GFG { static int k_nonzero_numbers ( string s , int n , int k ) { int [ , , ] dp = new int [ n + 1 , 2 , k + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) for ( int x = 0 ; x <= k ; x ++ ) dp [ i , j , x ] = 0 ; dp [ 0 , 0 , 0 ] = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int sm = 0 ; while ( sm < 2 ) { for ( int j = 0 ; j < k + 1 ; ++ j ) { int x = 0 ; while ( x <= ( sm != 0 ? 9 : s [ i ] - '0' ) ) { if ( j + ( x > 0 ? 1 : 0 ) < k + 1 ) { dp [ i + 1 , ( ( sm != 0 || x < ( s [ i ] - '0' ) ) ? 1 : 0 ) , j + ( x > 0 ? 1 : 0 ) ] += dp [ i , sm , j ] ; } ++ x ; } } ++ sm ; } } return dp [ n , 0 , k ] + dp [ n , 1 , k ] ; } public static void Main ( string [ ] args ) { string s = "25" ; int k = 2 ; int n = s . Length ; Console . Write ( k_nonzero_numbers ( s , n , k ) ) ; } }