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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100 ] [ 2 ] [ 10 ] [ 2 ] ; int noncoprimeCount ( int i , int N , string & S , bool bound , int prev , bool 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 ? ( S [ i ] - '0' ) : 9 ) ; ++ j ) { if ( ( __gcd ( j , prev ) != 1 ) || ( i == 0 ) allZeros == 1 ) { cnt += noncoprimeCount ( i + 1 , N , S , bound & ( j == ( S [ i ] - '0' ) ) , j , allZeros & ( j == 0 ) ) ; } } return val = cnt ; } void noncoprimeCountUtil ( int R ) { string S = to_string ( R ) ; int N = S . length ( ) ; memset ( dp , -1 , sizeof dp ) ; int ans = noncoprimeCount ( 0 , N , S , 1 , 0 , 1 ) ; cout << ans - 1 << endl ; } int main ( ) { int N = 10000 ; noncoprimeCountUtil ( N ) ; return 0 ; }