Count numbers ( smaller than or equal to N ) with given digit sum | Java program to count 2 s from 0 to n ; N can be max 10 ^ 18 and hence digitsum will be 162 maximum . ; If sum_so_far equals to given sum then return 1 else 0 ; Our constructed number should not become greater than N . ; If tight is true then it will also be true for ( i + 1 ) digit . ; Driver code
class GFG { static long dp [ ] [ ] [ ] = new long [ 18 ] [ 2 ] [ 162 ] ; static long solve ( int i , boolean tight , int sum_so_far , int Sum , String number , int len ) { if ( i == len ) { if ( sum_so_far == Sum ) return 1 ; else return 0 ; } long ans = dp [ i ] [ 1 ] [ sum_so_far ] ; if ( ans != - 1 ) { return ans ; } ans = 0 ; boolean ntight ; int nsum_so_far ; for ( char currdigit = '0' ; currdigit <= '9' ; currdigit ++ ) { if ( ! tight && currdigit > number . charAt ( i ) ) { break ; } ntight = tight || currdigit < number . charAt ( i ) ; nsum_so_far = sum_so_far + ( currdigit - '0' ) ; ans += solve ( i + 1 , ntight , nsum_so_far , Sum , number , len ) ; } return ans ; } public static void main ( String [ ] args ) { long count = 0 ; int sum = 4 ; String number = "100" ; for ( int i = 0 ; i < 18 ; i ++ ) { for ( int j = 0 ; j < 2 ; j ++ ) { for ( int k = 0 ; k < 162 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } System . out . println ( solve ( 0 , false , 0 , sum , number , number . length ( ) ) ) ; } }