Given an array arr[], the task is to count the number of unordered pairs (arr[i], arr[j]) from the given array such that (arr[i] * arr[j]) % 109 + 7 is equal to 1.
Example:
Input: arr[] = {2, 236426, 280311812, 500000004}
Output: 2
Explanation: Two such pairs from the given array are:
- (2 * 500000004) % 1000000007 = 1
- (236426 * 280311812) % 1000000007 = 1
Input: arr[] = {4434, 923094278, 6565}
Output: 1
Naive Approach: The simplest approach to solve the problem is to traverse the array and generate all possible pairs from the given array. For each pair, calculate their product modulo 109 + 7. If it is found to be equal to 1, increase count of such pairs. Finally, print the final count obtained.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, use the property that if (arr[i] * arr[j]) % 1000000007 =1, then arr[j] is modular inverse of arr[i] under modulo 109 + 7 which is always unique. Follow the steps given below to solve the problem:
- Initialize a Map hash, to store the frequencies of each element in the array arr[].
- Initialize a variable pairCount, to store the count of required pairs.
- Traverse the array and calculate modularInverse which is inverse of arr[i] under 109 + 7 and increase pairCount by hash[modularInverse] and decrease the count of pairCount by 1, if modularInverse is found to be equal to arr[i].
- Finally, print pairCount / 2 as the required answer as every pair has been counted twice by the above approach.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define MOD 1000000007// Iterative Function to calculate (x^y) % MODlong long int modPower(long long int x, long long int y){ // Initialize result long long int res = 1; // Update x if it exceeds MOD x = x % MOD; // If x is divisible by MOD if (x == 0) return 0; while (y > 0) { // If y is odd if (y & 1) // Multiply x with res res = (res * x) % MOD; // y must be even now y = y / 2; x = (x * x) % MOD; } return res;}// Function to count number of pairs// whose product modulo 1000000007 is 1int countPairs(long long int arr[], int N){ // Stores the count of // desired pairs int pairCount = 0; // Stores the frequencies of // each array element map<long long int, int> hash; // Traverse the array and update // frequencies in hash for (int i = 0; i < N; i++) { hash[arr[i]]++; } for (int i = 0; i < N; i++) { // Calculate modular inverse of // arr[i] under modulo 1000000007 long long int modularInverse = modPower(arr[i], MOD - 2); // Update desired count of pairs pairCount += hash[modularInverse]; // If arr[i] and its modular inverse // is equal under modulo MOD if (arr[i] == modularInverse) { // Updating count of desired pairs pairCount--; } } // Return the final count return pairCount / 2;}int main(){ long long int arr[] = { 2, 236426, 280311812, 500000004 }; int N = sizeof(arr) / sizeof(arr[0]); cout << countPairs(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ static final int MOD = 1000000007;// Iterative Function to calculate (x^y) % MODstatic long modPower(long x, int y){ // Initialize result long res = 1; // Update x if it exceeds MOD x = x % MOD; // If x is divisible by MOD if (x == 0) return 0; while (y > 0) { // If y is odd if (y % 2 == 1) // Multiply x with res res = (res * x) % MOD; // y must be even now y = y / 2; x = (x * x) % MOD; } return res;}// Function to count number of pairs// whose product modulo 1000000007 is 1static int countPairs(long arr[], int N){ // Stores the count of // desired pairs int pairCount = 0; // Stores the frequencies of // each array element HashMap<Long, Integer> hash = new HashMap<>(); // Traverse the array and update // frequencies in hash 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++) { // Calculate modular inverse of // arr[i] under modulo 1000000007 long modularInverse = modPower(arr[i], MOD - 2); // Update desired count of pairs if (hash.containsKey(modularInverse)) pairCount += hash.get(modularInverse); // If arr[i] and its modular inverse // is equal under modulo MOD if (arr[i] == modularInverse) { // Updating count of desired pairs pairCount--; } } // Return the final count return pairCount / 2;}// Driver codepublic static void main(String[] args){ long arr[] = { 2, 236426, 280311812, 500000004 }; int N = arr.length; System.out.print(countPairs(arr, N));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approachfrom collections import defaultdictMOD = 1000000007# Iterative Function to # calculate (x^y) % MODdef modPower(x, y): # Initialize result res = 1 # Update x if it exceeds # MOD x = x % MOD # If x is divisible by # MOD if (x == 0): return 0 while (y > 0): # If y is odd if (y & 1): # Multiply x with res res = (res * x) % MOD # y must be even now y = y // 2 x = (x * x) % MOD return res# Function to count number # of pairs whose product # modulo 1000000007 is 1def countPairs(arr, N): # Stores the count of # desired pairs pairCount = 0 # Stores the frequencies of # each array element hash1 = defaultdict(int) # Traverse the array and # update frequencies in hash for i in range(N): hash1[arr[i]] += 1 for i in range(N): # Calculate modular inverse # of arr[i] under modulo # 1000000007 modularInverse = modPower(arr[i], MOD - 2) # Update desired count of pairs pairCount += hash1[modularInverse] # If arr[i] and its modular # inverse is equal under # modulo MOD if (arr[i] == modularInverse): # Updating count of # desired pairs pairCount -= 1 # Return the final count return pairCount // 2# Driver codeif __name__ == "__main__": arr = [2, 236426, 280311812, 500000004] N = len(arr) print(countPairs(arr, N))# This code is contributed by Chitranayal |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ static int MOD = 1000000007;// Iterative Function to calculate (x^y) % MODstatic long modPower(long x, int y){ // Initialize result long res = 1; // Update x if it exceeds MOD x = x % MOD; // If x is divisible by MOD if (x == 0) return 0; while (y > 0) { // If y is odd if (y % 2 == 1) // Multiply x with res res = (res * x) % MOD; // y must be even now y = y / 2; x = (x * x) % MOD; } return res;}// Function to count number of pairs// whose product modulo 1000000007 is 1static int countPairs(long []arr, int N){ // Stores the count of // desired pairs int pairCount = 0; // Stores the frequencies of // each array element Dictionary<long, int> hash = new Dictionary<long, int>(); // Traverse the array and update // frequencies in hash for(int i = 0; i < N; i++) { if (hash.ContainsKey(arr[i])) { hash.Add(arr[i], hash[arr[i]] + 1); } else { hash.Add(arr[i], 1); } } for(int i = 0; i < N; i++) { // Calculate modular inverse of // arr[i] under modulo 1000000007 long modularInverse = modPower(arr[i], MOD - 2); // Update desired count of pairs if (hash.ContainsKey(modularInverse)) pairCount += hash[modularInverse]; // If arr[i] and its modular inverse // is equal under modulo MOD if (arr[i] == modularInverse) { // Updating count of desired pairs pairCount--; } } // Return the final count return pairCount / 2;}// Driver codepublic static void Main(){ long []arr = { 2, 236426, 280311812, 500000004 }; int N = arr.Length; Console.WriteLine(countPairs(arr, N));}}// This code is contributed by bgangwar59 |
Javascript
// JS program to implement// the above approachlet MOD = 1000000007// Iterative Function to // calculate (x^y) % MODfunction modPower(x, y){ // Initialize result let res = 1 // Update x if it exceeds // MOD x = x % MOD // If x is divisible by // MOD if (x == 0) return 0 while (y > 0) { // If y is odd if ((y & 1) == 1) // Multiply x with res res = (res * x) % MOD // y must be even now y = Math.floor(y / 2) x = (x * x) % MOD } return res}// Function to count number // of pairs whose product // modulo 1000000007 is 1function countPairs(arr, N){ // Stores the count of // desired pairs let pairCount = 0 // Stores the frequencies of // each array element hash1 = {} // Traverse the array and // update frequencies in hash for (var i = 0; i < N; i++) { if (!hash1.hasOwnProperty(arr[i])) hash1[arr[i]] = 0 hash1[arr[i]] += 1 } for (var i = 0; i < N; i++) { // Calculate modular inverse // of arr[i] under modulo // 1000000007 let modularInverse = modPower(arr[i], MOD - 2) // Update desired count of pairs if (!hash1.hasOwnProperty(modularInverse)) hash1[modularInverse] = 1 pairCount += hash1[modularInverse] // If arr[i] and its modular // inverse is equal under // modulo MOD if (arr[i] == modularInverse) // Updating count of // desired pairs pairCount -= 1 } // Return the final count return Math.floor(pairCount / 2)}// Driver codelet arr = [2, 236426, 280311812, 500000004]let N = arr.lengthconsole.log(countPairs(arr, N))// This code is contributed by phasing17 |
Output:
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
