Count pairs from an array having GCD equal to the minimum element in the pair | Java program for the above approach ; Function to count pairs from an array having GCD equal to minimum element of that pair ; Stores the resultant count ; Stores the frequency of each array element ; Traverse the array arr [ ] ; Iterate over the Map mp ; Stores the array element ; Stores the count of array element x ; If x is 1 ; Increment res by N - 1 ; Increment res by yC2 ; Iterate over the range [ 2 , sqrt ( x ) ] ; If x is divisible by j ; Increment the value of res by mp [ j ] ; If j is not equal to x / j ; Increment res by mp [ x / j ] ; Return the resultant count ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static int CountPairs ( int arr [ ] , int N ) { int res = 0 ; Map < Integer , Integer > mp = new HashMap < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { Integer c = mp . get ( arr [ i ] ) ; mp . put ( arr [ i ] , ( c == null ) ? 1 : c + 1 ) ; } Iterator < Map . Entry < Integer , Integer > > itr = mp . entrySet ( ) . iterator ( ) ; while ( itr . hasNext ( ) ) { Map . Entry < Integer , Integer > entry = itr . next ( ) ; int x = ( int ) entry . getKey ( ) ; int y = ( int ) entry . getValue ( ) ; if ( x == 1 ) { res += N - 1 ; continue ; } res += ( y * ( y - 1 ) ) / 2 ; for ( int j = 2 ; j <= Math . sqrt ( x ) ; j ++ ) { if ( x % j == 0 ) { res += mp . get ( j ) ; if ( j != x / j ) res += mp . get ( ( int ) x / j ) ; } } } return res ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 1 , 2 } ; int N = arr . length ; System . out . println ( CountPairs ( arr , N ) ) ; } }