Count numbers from a given range whose adjacent digits are not co |  ; Function to count numbers whose adjacent digits are not co - prime ; Base Case If the entire String is traversed ; If the subproblem has already been computed ; GCD of current and previous digits is not equal to 1 ; Current position is 0 ; All encountered digits until now are 0 s ; Return the total possible valid numbers ; Function to count numbers whose adjacent digits are not co - prime ; Convert R to String . ; Length of String ; Initialize dp array with - 1 ; Function call with initial values of bound , allZeros , previous as 1 , 1 , 0 ; Subtract 1 from the answer , as 0 is included ; Driver Code ; Input ; Function call
import java . util . * ; class GFG { static int [ ] [ ] [ ] [ ] dp = new int [ 100 ] [ 2 ] [ 10 ] [ 2 ] ; static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } static int noncoprimeCount ( int i , int N , char [ ] S , int bound , int prev , int allZeros ) { if ( i == N ) return 1 ; int val = dp [ i ] [ bound ] [ prev ] [ allZeros ] ; if ( val != - 1 ) return val ; int cnt = 0 ; for ( int j = 0 ; j <= ( bound != 0 ? ( S [ i ] - '0' ) : 9 ) ; ++ j ) { if ( ( __gcd ( j , prev ) != 1 ) || ( i == 0 ) allZeros == 1 ) { cnt += noncoprimeCount ( i + 1 , N , S , bound != 0 & ( j == ( S [ i ] - '0' ) ) ? 1 : 0 , j , ( allZeros != 0 & ( j == 0 ) ) ? 1 : 0 ) ; } } return val = cnt ; } static void noncoprimeCountUtil ( int R ) { String S = String . valueOf ( R ) ; int N = S . length ( ) ; for ( int i = 0 ; i < 100 ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) for ( int k = 0 ; k < 10 ; k ++ ) for ( int l = 0 ; l < 2 ; l ++ ) dp [ i ] [ j ] [ k ] [ l ] = - 1 ; int ans = noncoprimeCount ( 0 , N , S . toCharArray ( ) , 1 , 0 , 1 ) ; System . out . print ( ans - 1 + "NEW_LINE"); } public static void main ( String [ ] args ) { int N = 10000 ; noncoprimeCountUtil ( N ) ; } }