Count Numbers in Range with difference between Sum of digits at even and odd positions as Prime | Python implementation of the above approach ; Prime numbers upto 100 ; Function to return the count of required numbers from 0 to num ; Base Case ; check if the difference is equal to any prime number ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 1 , means number has already become smaller so we can place any digit , otherwise num [ pos ] ; If the current position is odd add it to currOdd , otherwise to currEven ; Function to convert x into its digit vector and uses count ( ) function to return the required count ; Initialize dp ; Driver Code
M = 18 NEW_LINE prime = [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 ] NEW_LINE def count ( pos , even , odd , tight , num ) : NEW_LINE INDENT if pos == len ( num ) : NEW_LINE INDENT if len ( num ) & 1 : NEW_LINE INDENT odd , even = even , odd NEW_LINE DEDENT d = even - odd NEW_LINE for i in range ( 24 ) : NEW_LINE INDENT if d == prime [ i ] : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT return 0 NEW_LINE DEDENT if dp [ pos ] [ even ] [ odd ] [ tight ] != - 1 : NEW_LINE INDENT return dp [ pos ] [ even ] [ odd ] [ tight ] NEW_LINE DEDENT ans = 0 NEW_LINE limit = 9 if tight else num [ pos ] NEW_LINE for d in range ( limit + 1 ) : NEW_LINE INDENT currF = tight NEW_LINE currEven = even NEW_LINE currOdd = odd NEW_LINE if d < num [ pos ] : NEW_LINE INDENT currF = 1 NEW_LINE DEDENT if pos & 1 : NEW_LINE INDENT currOdd += d NEW_LINE DEDENT else : NEW_LINE INDENT currEven += d NEW_LINE DEDENT ans += count ( pos + 1 , currEven , currOdd , currF , num ) NEW_LINE DEDENT dp [ pos ] [ even ] [ odd ] [ tight ] = ans NEW_LINE return dp [ pos ] [ even ] [ odd ] [ tight ] NEW_LINE DEDENT def solve ( x ) : NEW_LINE INDENT global dp NEW_LINE num = [ ] NEW_LINE while x : NEW_LINE INDENT num . append ( x % 10 ) NEW_LINE x //= 10 NEW_LINE DEDENT num . reverse ( ) NEW_LINE dp = [ [ [ [ - 1 , - 1 ] for i in range ( 90 ) ] for j in range ( 90 ) ] for k in range ( M ) ] NEW_LINE return count ( 0 , 0 , 0 , 0 , num ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT dp = [ ] NEW_LINE L = 1 NEW_LINE R = 50 NEW_LINE print ( solve ( R ) - solve ( L - 1 ) ) NEW_LINE L = 50 NEW_LINE R = 100 NEW_LINE print ( solve ( R ) - solve ( L - 1 ) ) NEW_LINE DEDENT