Count numbers with exactly K non | Java program to count the numbers having exactly K non - zero digits and sum of digits are odd and distinct . ; To store digits of N ; visited map ; DP Table ; Push all the digits of N into digits vector ; Function returns the count ; If desired number is formed whose sum is odd ; If it is not present in map , mark it as true and return 1 ; Sum is present in map already ; Desired result not found ; If that state is already calculated just return that state value ; Upper limit ; To store the count of desired numbers ; If k is non - zero , i ranges from 0 to j else [ 1 , j ] ; If current digit is 0 , decrement k and recurse sum is not changed as we are just adding 0 that makes no difference ; If i is non zero , then k remains unchanged and value is added to sum ; Memoize and return ; Driver code ; K is the number of exact non - zero elements to have in number ; break N into its digits ; We keep record of 0 s we need to place in the number
import java . util . * ; class GFG { static Vector < Integer > digits = new Vector < Integer > ( ) ; static boolean [ ] vis = new boolean [ 170 ] ; static int [ ] [ ] [ ] [ ] dp = new int [ 19 ] [ 19 ] [ 2 ] [ 170 ] ; static void ConvertIntoDigit ( int n ) { while ( n > 0 ) { int dig = n % 10 ; digits . add ( dig ) ; n /= 10 ; } Collections . reverse ( digits ) ; } static int solve ( int idx , int k , int tight , int sum ) { if ( idx == digits . size ( ) && k == 0 && sum % 2 == 1 ) { if ( ! vis [ sum ] ) { vis [ sum ] = true ; return 1 ; } return 0 ; } if ( idx > digits . size ( ) ) { return 0 ; } if ( dp [ idx ] [ k ] [ tight ] [ sum ] > 0 ) { return dp [ idx ] [ k ] [ tight ] [ sum ] ; } int j ; if ( idx < digits . size ( ) && tight == 0 ) { j = digits . get ( idx ) ; } else { j = 9 ; } int cnt = 0 ; for ( int i = ( k > 0 ? 0 : 1 ) ; i <= j ; i ++ ) { int newtight = tight ; if ( i < j ) { newtight = 1 ; } if ( i == 0 ) cnt += solve ( idx + 1 , k - 1 , newtight , sum ) ; else cnt += solve ( idx + 1 , k , newtight , sum + i ) ; } return dp [ idx ] [ k ] [ tight ] [ sum ] = cnt ; } public static void main ( String [ ] args ) { int N , k ; N = 169 ; k = 2 ; ConvertIntoDigit ( N ) ; k = digits . size ( ) - k ; System . out . print ( solve ( 0 , k , 0 , 0 ) ) ; } }