Count Numbers in Range with difference between Sum of digits at even and odd positions as Prime | C # 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
using System ; using System . Collections . Generic ; class GFG { static int M = 18 ; static int a , b ; static int [ , , , ] dp = new int [ M , 90 , 90 , 2 ] ; static int [ ] 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 } ; static int count ( int pos , int even , int odd , int tight , List < int > num ) { if ( pos == num . Count ) { if ( ( num . Count & 1 ) != 0 ) { int t = odd ; odd = even ; even = t ; } int d = even - odd ; for ( int 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 ] ; int ans = 0 ; int limit = ( tight != 0 ? 9 : num [ pos ] ) ; for ( int d = 0 ; d <= limit ; d ++ ) { int currF = tight , currEven = even ; int currOdd = odd ; if ( d < num [ pos ] ) currF = 1 ; if ( ( pos & 1 ) != 0 ) currOdd += d ; else currEven += d ; ans += count ( pos + 1 , currEven , currOdd , currF , num ) ; } return dp [ pos , even , odd , tight ] = ans ; } static int solve ( int x ) { List < int > num = new List < int > ( ) ; while ( x != 0 ) { num . Add ( x % 10 ) ; x /= 10 ; } num . Reverse ( ) ; for ( int i = 0 ; i < dp . GetLength ( 0 ) ; i ++ ) for ( int j = 0 ; j < dp . GetLength ( 1 ) ; j ++ ) for ( int k = 0 ; k < dp . GetLength ( 2 ) ; k ++ ) for ( int k1 = 0 ; k1 < dp . GetLength ( 3 ) ; k1 ++ ) dp [ i , j , k , k1 ] = - 1 ; return count ( 0 , 0 , 0 , 0 , num ) ; } public static void Main ( String [ ] args ) { int L = 1 , R = 50 ; Console . WriteLine ( solve ( R ) - solve ( L - 1 ) ) ; L = 50 ; R = 100 ; Console . WriteLine ( solve ( R ) - solve ( L - 1 ) ) ; } }