Count pairs whose product modulo 10 ^ 9 + 7 is equal to 1 | Java program to implement the above approach ; Iterative Function to calculate ( x ^ y ) % MOD ; Initialize result ; Update x if it exceeds MOD ; If x is divisible by MOD ; If y is odd ; Multiply x with res ; y must be even now ; Function to count number of pairs whose product modulo 1000000007 is 1 ; Stores the count of desired pairs ; Stores the frequencies of each array element ; Traverse the array and update frequencies in hash ; Calculate modular inverse of arr [ i ] under modulo 1000000007 ; Update desired count of pairs ; If arr [ i ] and its modular inverse is equal under modulo MOD ; Updating count of desired pairs ; Return the final count ; Driver code
import java . util . * ; class GFG { static final int MOD = 1000000007 ; static long modPower ( long x , int y ) { long res = 1 ; x = x % MOD ; if ( x == 0 ) return 0 ; while ( y > 0 ) { if ( y % 2 == 1 ) res = ( res * x ) % MOD ; y = y / 2 ; x = ( x * x ) % MOD ; } return res ; } static int countPairs ( long arr [ ] , int N ) { int pairCount = 0 ; HashMap < Long , Integer > hash = new HashMap < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( hash . containsKey ( arr [ i ] ) ) { hash . put ( arr [ i ] , hash . get ( arr [ i ] ) + 1 ) ; } else { hash . put ( arr [ i ] , 1 ) ; } } for ( int i = 0 ; i < N ; i ++ ) { long modularInverse = modPower ( arr [ i ] , MOD - 2 ) ; if ( hash . containsKey ( modularInverse ) ) pairCount += hash . get ( modularInverse ) ; if ( arr [ i ] == modularInverse ) { pairCount -- ; } } return pairCount / 2 ; } public static void main ( String [ ] args ) { long arr [ ] = { 2 , 236426 , 280311812 , 500000004 } ; int N = arr . length ; System . out . print ( countPairs ( arr , N ) ) ; } }