Count numbers in given range such that sum of even digits is greater than sum of odd digits | Python code to count number in the range having the sum of even digits greater than the sum of odd digits ; Base Case ; check if condition satisfied or not ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 0 , means number has already become smaller so we can place any digit , otherwise num [ index ] ; if current digit is odd ; if current digit is even ; Function to convert n into its digit vector and uses memo ( ) function to return the required count ; Initialize dp ; Driver Code
def memo ( index , evenSum , oddSum , tight ) : NEW_LINE INDENT if index == len ( v ) : NEW_LINE INDENT if evenSum > oddSum : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if dp [ index ] [ evenSum ] [ oddSum ] [ tight ] != - 1 : NEW_LINE INDENT return dp [ index ] [ evenSum ] [ oddSum ] [ tight ] NEW_LINE DEDENT limit = v [ index ] if tight else 9 NEW_LINE ans = 0 NEW_LINE for d in range ( limit + 1 ) : NEW_LINE INDENT currTight = 0 NEW_LINE if d == v [ index ] : NEW_LINE INDENT currTight = tight NEW_LINE DEDENT if d % 2 != 0 : NEW_LINE INDENT ans += memo ( index + 1 , evenSum , oddSum + d , currTight ) NEW_LINE DEDENT else : NEW_LINE INDENT ans += memo ( index + 1 , evenSum + d , oddSum , currTight ) NEW_LINE DEDENT DEDENT dp [ index ] [ evenSum ] [ oddSum ] [ tight ] = ans NEW_LINE return ans NEW_LINE DEDENT def countNum ( n ) : NEW_LINE INDENT global dp , v NEW_LINE v . clear ( ) NEW_LINE num = [ ] NEW_LINE while n : NEW_LINE INDENT v . append ( n % 10 ) NEW_LINE n //= 10 NEW_LINE DEDENT v . reverse ( ) NEW_LINE dp = [ [ [ [ - 1 , - 1 ] for i in range ( 180 ) ] for j in range ( 180 ) ] for k in range ( 18 ) ] NEW_LINE return memo ( 0 , 0 , 0 , 1 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT dp = [ ] NEW_LINE v = [ ] NEW_LINE L = 2 NEW_LINE R = 10 NEW_LINE print ( countNum ( R ) - countNum ( L - 1 ) ) NEW_LINE DEDENT