Count total number of N digit numbers such that the difference between sum of even and odd digits is 1 | 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 the current digit is odd , then add it to odd sum and recur ; 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 Code ; A lookup table used for memoization .
def countRec ( digits , esum , osum , isOdd , n ) : NEW_LINE INDENT if digits == n : NEW_LINE INDENT return ( esum - osum == 1 ) NEW_LINE DEDENT if lookup [ digits ] [ esum ] [ osum ] [ isOdd ] != - 1 : NEW_LINE INDENT return lookup [ digits ] [ esum ] [ osum ] [ isOdd ] NEW_LINE DEDENT ans = 0 NEW_LINE if isOdd : NEW_LINE INDENT for i in range ( 10 ) : NEW_LINE INDENT ans += countRec ( digits + 1 , esum , osum + i , False , n ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for i in range ( 10 ) : NEW_LINE INDENT ans += countRec ( digits + 1 , esum + i , osum , True , n ) NEW_LINE DEDENT DEDENT lookup [ digits ] [ esum ] [ osum ] [ isOdd ] = ans NEW_LINE return ans NEW_LINE DEDENT def finalCount ( n ) : NEW_LINE INDENT global lookup NEW_LINE digits = 0 NEW_LINE lookup = [ [ [ [ - 1 , - 1 ] for i in range ( 500 ) ] for j in range ( 500 ) ] for k in range ( 50 ) ] NEW_LINE ans = 0 NEW_LINE esum = 0 NEW_LINE osum = 0 NEW_LINE for i in range ( 1 , 10 ) : NEW_LINE INDENT ans += countRec ( digits + 1 , esum + i , osum , True , n ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT lookup = [ ] NEW_LINE n = 3 NEW_LINE print ( " Count ▁ of ▁ % d ▁ digit ▁ numbers ▁ is ▁ % d " % ( n , finalCount ( n ) ) ) NEW_LINE DEDENT