Cuente los pares cuyo producto módulo 10^9 + 7 sea igual a 1

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: 

  1. (2 * 500000004) % 1000000007 = 1
  2. (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)

Publicación traducida automáticamente

Artículo escrito por doreamon_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *