Cuente los pares (i, j) de los arreglos arr[] & brr[] tales que arr[i] – brr[j] = arr[j] – brr[i]

Dados dos arreglos arr[] y brr[] que consisten en N enteros, la tarea es contar el número de pares (i, j) de ambos arreglos de modo que (arr[i] – brr[j]) y (arr[ j] – brr[i]) son iguales.

Ejemplos:

Entrada: A[] = {1, 2, 3, 2, 1}, B[] = {1, 2, 3, 2, 1}
Salida: 2
Explicación: Los pares que cumplen la condición son:

(1, 5): arr[1] – brr[5] = 1 – 1 = 0, arr[5[ – brr[1] = 1 – 1 = 0

(2, 4): arr[2] – brr[4] = 2 – 2 = 0, arr[4] – brr[2] = 2 – 2 = 0

Entrada: A [] = {1, 4, 20, 3, 10, 5}, B[] = {9, 6, 1, 7, 11, 6}
Salida: 4

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares a partir de dos arrays dadas y verificar la condición requerida. Por cada par para el que se encuentre que la condición es verdadera, aumente el conteo de tales pares. Finalmente, imprima el conteo obtenido.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea es transformar la expresión dada (a[i] – b[j] = a[j] – b[i]) en la forma (a[i] + b[i] = a[j] + b[j]) y luego calcular los pares que satisfacen la condición. A continuación se muestran los pasos:

Transforme la expresión, a[i] – b[j] = a[j] – b[i] ==> a[i] + b[i] = a[j] +b[j] . La forma general de expresión se convierte en contar la suma de valores en cada índice correspondiente de las dos arrays para cualquier par (i, j) .
Inicialice una array auxiliar c[] para almacenar la suma correspondiente c[i] = a[i] + b[i] en cada índice i .
Ahora el problema se reduce a encontrar el número de pares posibles que tienen el mismo valor de c[i] .
Cuente la frecuencia de cada elemento en la array c[] y si cualquier valor de frecuencia c[i] es mayor que uno, entonces puede formar un par.
Cuente el número de pares válidos en los pasos anteriores usando la fórmula:

$\frac{c[i]*(c[i] - 1)}{2}$

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the pairs such that
// given condition is satisfied
int CountPairs(int* a, int* b, int n)
{
    // Stores the sum of element at
    // each corresponding index
    int C[n];
 
    // Find the sum of each index
    // of both array
    for (int i = 0; i < n; i++) {
        C[i] = a[i] + b[i];
    }
 
    // Stores frequency of each element
    // present in sumArr
    map<int, int> freqCount;
 
    for (int i = 0; i < n; i++) {
        freqCount[C[i]]++;
    }
 
    // Initialize number of pairs
    int NoOfPairs = 0;
 
    for (auto x : freqCount) {
        int y = x.second;
 
        // Add possible valid pairs
        NoOfPairs = NoOfPairs
                    + y * (y - 1) / 2;
    }
 
    // Return Number of Pairs
    cout << NoOfPairs;
}
 
// Driver Code
int main()
{
    // Given array arr[] and brr[]
    int arr[] = { 1, 4, 20, 3, 10, 5 };
 
    int brr[] = { 9, 6, 1, 7, 11, 6 };
 
    // Size of given array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function calling
    CountPairs(arr, brr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
import java.io.*;
 
class GFG{
     
// Function to find the minimum number
// needed to be added so that the sum
// of the digits does not exceed K
static void CountPairs(int a[], int b[], int n)
{
     
    // Stores the sum of element at
    // each corresponding index
    int C[] = new int[n];
   
    // Find the sum of each index
    // of both array
    for(int i = 0; i < n; i++)
    {
        C[i] = a[i] + b[i];
    }
     
    // Stores frequency of each element
    // present in sumArr
    // map<int, int> freqCount;
    HashMap<Integer,
            Integer> freqCount = new HashMap<>();
   
    for(int i = 0; i < n; i++)
    {
        if (!freqCount.containsKey(C[i]))
            freqCount.put(C[i], 1);
        else
            freqCount.put(C[i],
            freqCount.get(C[i]) + 1);
    }
   
    // Initialize number of pairs
    int NoOfPairs = 0;
   
    for(Map.Entry<Integer,
                  Integer> x : freqCount.entrySet())
    {
        int y = x.getValue();
   
        // Add possible valid pairs
        NoOfPairs = NoOfPairs +
                  y * (y - 1) / 2;
    }
   
    // Return Number of Pairs
   System.out.println(NoOfPairs);
}
 
// Driver Code
public static void main(String args[])
{
   
    // Given array arr[] and brr[]
    int arr[] = { 1, 4, 20, 3, 10, 5 };
    int brr[] = { 9, 6, 1, 7, 11, 6 };
     
    // Size of given array
    int N = arr.length;
     
    // Function calling
    CountPairs(arr, brr, N);
}
}
 
// This code is contributed by bikram2001jha

Python3

# Python3 program for the above approach
 
# Function to count the pairs such that
# given condition is satisfied
def CountPairs(a, b, n):
     
    # Stores the sum of element at
    # each corresponding index
    C = [0] * n
  
    # Find the sum of each index
    # of both array
    for i in range(n):
        C[i] = a[i] + b[i]
     
    # Stores frequency of each element
    # present in sumArr
    freqCount = dict()
  
    for i in range(n):
        if C[i] in freqCount.keys():
            freqCount[C[i]] += 1
        else:
            freqCount[C[i]] = 1
  
    # Initialize number of pairs
    NoOfPairs = 0
  
    for x in freqCount:
        y = freqCount[x]
  
        # Add possible valid pairs
        NoOfPairs = (NoOfPairs + y *
                       (y - 1) // 2)
     
    # Return Number of Pairs
    print(NoOfPairs)
 
# Driver Code
 
# Given array arr[] and brr[]
arr = [ 1, 4, 20, 3, 10, 5 ]
brr = [ 9, 6, 1, 7, 11, 6 ]
  
# Size of given array
N = len(arr)
  
# Function calling
CountPairs(arr, brr, N)
 
# This code is contributed by code_hunt

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the minimum number
// needed to be added so that the sum
// of the digits does not exceed K
static void CountPairs(int []a, int []b,
                       int n)
{
     
    // Stores the sum of element at
    // each corresponding index
    int []C = new int[n];
   
    // Find the sum of each index
    // of both array
    for(int i = 0; i < n; i++)
    {
        C[i] = a[i] + b[i];
    }
     
    // Stores frequency of each element
    // present in sumArr
    // map<int, int> freqCount;
    Dictionary<int,
               int> freqCount = new Dictionary<int,
                                               int>();
   
    for(int i = 0; i < n; i++)
    {
        if (!freqCount.ContainsKey(C[i]))
            freqCount.Add(C[i], 1);
        else
            freqCount[C[i]] = freqCount[C[i]] + 1;
    }
   
    // Initialize number of pairs
    int NoOfPairs = 0;
   
    foreach(KeyValuePair<int,
                         int> x in freqCount)
    {
        int y = x.Value;
   
        // Add possible valid pairs
        NoOfPairs = NoOfPairs +
                  y * (y - 1) / 2;
    }
     
    // Return Number of Pairs
    Console.WriteLine(NoOfPairs);
}
 
// Driver Code
public static void Main(String []args)
{
     
    // Given array []arr and brr[]
    int []arr = { 1, 4, 20, 3, 10, 5 };
    int []brr = { 9, 6, 1, 7, 11, 6 };
     
    // Size of given array
    int N = arr.Length;
     
    // Function calling
    CountPairs(arr, brr, N);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count the pairs such that
// given condition is satisfied
function CountPairs(a,b, n)
{
    // Stores the sum of element at
    // each corresponding index
    var C = Array(n);
 
    // Find the sum of each index
    // of both array
    for (var i = 0; i < n; i++) {
        C[i] = a[i] + b[i];
    }
 
    // Stores frequency of each element
    // present in sumArr
    var freqCount = new Map();
 
    for (var i = 0; i < n; i++) {
        if(freqCount.has(C[i]))
            freqCount.set(C[i], freqCount.get(C[i])+1)
        else
            freqCount.set(C[i], 1)
    }
 
    // Initialize number of pairs
    var NoOfPairs = 0;
 
    freqCount.forEach((value, key) => {
         
        var y = value;
 
        // Add possible valid pairs
        NoOfPairs = NoOfPairs
                    + y * (y - 1) / 2;
    });
 
    // Return Number of Pairs
    document.write( NoOfPairs);
}
 
// Driver Code
 
// Given array arr[] and brr[]
var arr = [1, 4, 20, 3, 10, 5];
var brr = [ 9, 6, 1, 7, 11, 6 ];
 
// Size of given array
var N = arr.length;
 
// Function calling
CountPairs(arr, brr, N);
 
</script>

Producción:

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta