Dada una array arr[] , la tarea es contar el número de pares no ordenados (arr[i], arr[j]) de la array dada tal que (arr[i] * arr[j]) % 10 9 + 7 es igual a 1
Ejemplo:
Entrada: arr[] = {2, 236426, 280311812, 500000004}
Salida: 2
Explicación: Dos de estos pares de la array dada son:
- (2 * 500000004) % 1000000007 = 1
- (236426 * 280311812) % 1000000007 = 1
Entrada: arr[] = {4434, 923094278, 6565}
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y generar todos los pares posibles a partir de la array dada . Para cada par, calcule su producto módulo 10 9 + 7 . Si se encuentra que es igual a 1 , aumente la cuenta de dichos pares. Finalmente, imprima el conteo final obtenido.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, use la propiedad de que si (arr[i] * arr[j]) % 1000000007 =1 , entonces arr[j] es el inverso modular de arr[i] bajo módulo 10 9 + 7 que siempre es único. Siga los pasos que se indican a continuación para resolver el problema:
- Inicialice un mapa hash para almacenar las frecuencias de cada elemento en la array arr[] .
- Inicialice una variable pairCount para almacenar el recuento de pares requeridos.
- Recorra la array y calcule modularInverse , que es el inverso de arr[i] por debajo de 10 9 + 7 y aumente pairCount en hash[modularInverse] y disminuya el recuento de pairCount en 1 , si se encuentra que modularInverse es igual a arr[i] .
- Finalmente, imprima pairCount / 2 como la respuesta requerida ya que cada par ha sido contado dos veces por el método anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
// Iterative Function to calculate (x^y) % MOD
long 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 1
int 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 approach
import java.util.*;
class GFG{
static final int MOD = 1000000007;
// Iterative Function to calculate (x^y) % MOD
static 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 1
static 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 code
public 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 approach from collections import defaultdict MOD = 1000000007 # Iterative Function to # calculate (x^y) % MOD def 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 1 def 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 code if __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 approach
using System;
using System.Collections.Generic;
class GFG{
static int MOD = 1000000007;
// Iterative Function to calculate (x^y) % MOD
static 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 1
static 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 code
public static void Main()
{
long []arr = { 2, 236426, 280311812, 500000004 };
int N = arr.Length;
Console.WriteLine(countPairs(arr, N));
}
}
// This code is contributed by bgangwar59
Producción:
2
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)