Number of Co | Java program to count the pairs whose sum of digits is co - prime ; Recursive function to return the frequency of numbers having their sum of digits i ; Returns 1 or 0 ; Returns value of the dp if already stored ; Loop from digit 0 to 9 ; To change the tight to 1 ; Calling the recursive function to find the frequency ; Function to find out frequency of numbers from 1 to N having their sum of digits from 1 to 162 and store them in array ; Number to string conversion ; Calling the recursive function and pushing it into array ; Function to find the pairs ; Calling the formArray function of a - 1 numbers ; Calling the formArray function of b numbers ; Subtracting the frequency of higher number array with lower number array and thus finding the range of numbers from a to b having sum from 1 to 162 ; To find out total number of pairs which are co - prime ; Driver code ; Function to count the pairs
import java . io . * ; import java . util . * ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static long recursive ( long idx , long sum , long tight , String st , long [ ] [ ] [ ] dp , long num ) { if ( idx == num ) { return sum == 0 ? 1 : 0 ; } if ( dp [ ( int ) idx ] [ ( int ) tight ] [ ( int ) sum ] != - 1 ) return dp [ ( int ) idx ] [ ( int ) tight ] [ ( int ) sum ] ; long newTight ; long ans = 0 ; long d ; for ( d = 0 ; d < 10 ; ++ d ) { newTight = 0 ; if ( tight == 1 && st . charAt ( ( int ) idx ) - '0' < d ) continue ; if ( tight == 1 && st . charAt ( ( int ) idx ) - '0' == d ) newTight = 1 ; if ( sum >= d ) ans += recursive ( idx + 1 , sum - d , ( int ) newTight , st , dp , num ) ; } return dp [ ( int ) idx ] [ ( int ) tight ] [ ( int ) sum ] = ans ; } static ArrayList < Long > formArray ( long N ) { long [ ] [ ] [ ] dp = new long [ 20 ] [ 2 ] [ 166 ] ; for ( long [ ] [ ] innerRow : dp ) { for ( long [ ] innerInnerRow : innerRow ) { Arrays . fill ( innerInnerRow , - 1 ) ; } } String st = String . valueOf ( N ) ; long num = st . length ( ) ; ArrayList < Long > arr = new ArrayList < Long > ( ) ; for ( int i = 1 ; i <= 162 ; ++ i ) { arr . add ( recursive ( 0 , i , 1 , st , dp , num ) ) ; } return arr ; } static long findPair ( long a , long b ) { ArrayList < Long > arr_smaller = formArray ( a - 1 ) ; ArrayList < Long > arr_greater = formArray ( b ) ; for ( int i = 0 ; i < arr_greater . size ( ) ; ++ i ) { arr_greater . set ( i , arr_greater . get ( i ) - arr_smaller . get ( i ) ) ; } long ans = 0 ; for ( int i = 1 ; i <= 162 ; ++ i ) { for ( int j = i + 1 ; j <= 162 ; ++ j ) { if ( gcd ( i , j ) == 1 ) { ans = ( ans + arr_greater . get ( i - 1 ) * arr_greater . get ( j - 1 ) ) ; } } } return ans ; } public static void main ( String [ ] args ) { long a = 12 , b = 15 ; System . out . println ( findPair ( a , b ) ) ; } }