Count numbers with exactly K non | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > digits ; bool vis [ 170 ] = { false } ; int dp [ 19 ] [ 19 ] [ 2 ] [ 170 ] ; void ConvertIntoDigit ( int n ) { while ( n ) { int dig = n % 10 ; digits . push_back ( dig ) ; n /= 10 ; } reverse ( digits . begin ( ) , digits . end ( ) ) ; } int solve ( int idx , int k , int tight , int sum ) { if ( idx == digits . size ( ) && k == 0 && sum & 1 ) { if ( ! vis [ sum ] ) { vis [ sum ] = 1 ; return 1 ; } return 0 ; } if ( idx > digits . size ( ) ) { return 0 ; } if ( dp [ idx ] [ k ] [ tight ] [ sum ] ) { return dp [ idx ] [ k ] [ tight ] [ sum ] ; } int j ; if ( tight == 0 ) { j = digits [ idx ] ; } else { j = 9 ; } int cnt = 0 ; for ( int i = ( k ? 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 ; } int main ( ) { int N , k ; N = 169 , k = 2 ; ConvertIntoDigit ( N ) ; k = digits . size ( ) - k ; cout << solve ( 0 , k , 0 , 0 ) ; }