Count Numbers in Range with difference between Sum of digits at even and odd positions as Prime | JavaScript 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
var M = 18 ; var a , b ; var dp = Array . from ( Array ( M ) , ( ) => Array ( 90 ) ) ; var 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 ] ; function count ( pos , even , odd , tight , num ) { if ( pos == num . length ) { if ( num . length & 1 ) [ odd , even ] = [ even , odd ] var d = even - odd ; for ( var i = 0 ; i < 24 ; i ++ ) if ( d == prime [ i ] ) return 1 ; return 0 ; } if ( dp [ pos ] [ even ] [ odd ] [ tight ] != - 1 ) return dp [ pos ] [ even ] [ odd ] [ tight ] ; var ans = 0 ; var limit = ( tight ? 9 : num [ pos ] ) ; for ( var d = 0 ; d <= limit ; d ++ ) { var currF = tight , currEven = even ; var currOdd = odd ; if ( d < num [ pos ] ) currF = 1 ; if ( pos & 1 ) currOdd += d ; else currEven += d ; ans += count ( pos + 1 , currEven , currOdd , currF , num ) ; } return dp [ pos ] [ even ] [ odd ] [ tight ] = ans ; } function solve ( x ) { var num = [ ] ; while ( x ) { num . push ( x % 10 ) ; x = parseInt ( x / 10 ) ; } num . reverse ( ) ; for ( var i = 0 ; i < M ; i ++ ) for ( var j = 0 ; j < 90 ; j ++ ) dp [ i ] [ j ] = Array . from ( Array ( 90 ) , ( ) => Array ( 2 ) . fill ( - 1 ) ) return count ( 0 , 0 , 0 , 0 , num ) ; } var L = 1 , R = 50 ; document . write ( solve ( R ) - solve ( L - 1 ) + " " ) ; L = 50 , R = 100 ; document . write ( solve ( R ) - solve ( L - 1 ) ) ;