Number of Co | Javascript 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
function gcd ( a , b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } function recursive ( idx , sum , tight , st , dp , num ) { if ( idx == num ) { return sum == 0 ? 1 : 0 ; } if ( dp [ idx ] [ tight ] [ sum ] != - 1 ) return dp [ idx ] [ tight ] [ sum ] ; let newTight ; let ans = 0 ; let d ; for ( d = 0 ; d < 10 ; ++ d ) { newTight = 0 ; if ( tight == 1 && st [ idx ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) < d ) continue ; if ( tight == 1 && st [ idx ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) == d ) newTight = 1 ; if ( sum >= d ) ans += recursive ( idx + 1 , sum - d , newTight , st , dp , num ) ; } return dp [ idx ] [ tight ] [ sum ] = ans ; } function formArray ( N ) { let dp = new Array ( 20 ) ; for ( let i = 0 ; i < 20 ; i ++ ) { dp [ i ] = new Array ( 2 ) ; for ( let j = 0 ; j < 2 ; j ++ ) { dp [ i ] [ j ] = new Array ( 166 ) ; for ( let k = 0 ; k < 166 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } let st = ( N ) . toString ( ) ; let num = st . length ; let arr = [ ] ; for ( let i = 1 ; i <= 162 ; ++ i ) { arr . push ( recursive ( 0 , i , 1 , st , dp , num ) ) ; } return arr ; } function findPair ( a , b ) { let arr_smaller = formArray ( a - 1 ) ; let arr_greater = formArray ( b ) ; for ( let i = 0 ; i < arr_greater . length ; ++ i ) { arr_greater [ i ] -= arr_smaller [ i ] ; } let ans = 0 ; for ( let i = 1 ; i <= 162 ; ++ i ) { for ( let j = i + 1 ; j <= 162 ; ++ j ) { if ( gcd ( i , j ) == 1 ) { ans = ( ans + arr_greater [ i - 1 ] * arr_greater [ j - 1 ] ) ; } } } return ans ; } let a = 12 , b = 15 ; document . write ( findPair ( a , b ) ) ;