Count total number of N digit numbers such that the difference between sum of even and odd digits is 1 | A memoization based recursive program to count numbers with difference between odd and even digit sums as 1 ; A lookup table used for memoization . ; Memoization based recursive function to count numbers with even and odd digit sum difference as 1. This function considers leading zero as a digit ; Base Case ; If current subproblem is already computed ; Initialize result ; If current digit is odd , then add it to odd sum and recur ; else Add to even sum and recur ; Store current result in lookup table and return the same ; This is mainly a wrapper over countRec . It explicitly handles leading digit and calls countRec ( ) for remaining digits . ; Initialize number digits considered so far ; Initialize all entries of lookup table ; Initialize final answer ; Initialize even and odd sums ; Explicitly handle first digit and call recursive function countRec for remaining digits . Note that the first digit is considered as even digit . ; Driver program
class GFG { static int [ ] [ ] [ ] [ ] lookup = new int [ 50 ] [ 1000 ] [ 1000 ] [ 2 ] ; static int countRec ( int digits , int esum , int osum , int isOdd , int n ) { if ( digits == n ) return ( esum - osum == 1 ) ? 1 : 0 ; if ( lookup [ digits ] [ esum ] [ osum ] [ isOdd ] != - 1 ) return lookup [ digits ] [ esum ] [ osum ] [ isOdd ] ; int ans = 0 ; if ( isOdd == 1 ) for ( int i = 0 ; i <= 9 ; i ++ ) ans += countRec ( digits + 1 , esum , osum + i , 0 , n ) ; for ( int i = 0 ; i <= 9 ; i ++ ) ans += countRec ( digits + 1 , esum + i , osum , 1 , n ) ; return lookup [ digits ] [ esum ] [ osum ] [ isOdd ] = ans ; } static int finalCount ( int n ) { int digits = 0 ; for ( int i = 0 ; i < 50 ; i ++ ) for ( int j = 0 ; j < 1000 ; j ++ ) for ( int k = 0 ; k < 1000 ; k ++ ) for ( int l = 0 ; l < 2 ; l ++ ) lookup [ i ] [ j ] [ k ] [ l ] = - 1 ; int ans = 0 ; int esum = 0 , osum = 0 ; for ( int i = 1 ; i <= 9 ; i ++ ) ans += countRec ( digits + 1 , esum + i , osum , 1 , n ) ; return ans ; } public static void main ( String [ ] args ) { int n = 3 ; System . out . println ( " Count ▁ of ▁ " + n + " ▁ digit ▁ numbers ▁ is ▁ " + finalCount ( n ) ) ; } }