Dadas cuatro arrays que contienen elementos enteros y una suma de enteros , la tarea es contar los cuatrillizos de modo que cada elemento se elija de una array diferente y la suma de los cuatro elementos sea igual a la suma dada .
Ejemplos:
Entrada: P[] = {0, 2}, Q[] = {-1, -2}, R[] = {2, 1}, S[] = {2, -1}, sum = 0
Salida: 2
(0, -1, 2, -1) y (2, -2, 1, -1) son los cuatrillizos requeridos.Entrada: P[] = {1, -1, 2, 3, 4}, Q[] = {3, 2, 4}, R[] = {-2, -1, 2, 1}, S[] = {4, -1}, suma = 3
Salida: 10
Enfoque: Se han discutido dos enfoques diferentes para resolver este problema en el Conjunto 1 y el Conjunto 2 de este artículo. Aquí, se discutirá un enfoque que utiliza la búsqueda binaria .
Elija dos arrays y calcule todas las sumas de pares posibles y guárdelas en un vector. Ahora, elija las otras dos arrays y calcule todas las sumas posibles y para cada suma diga tempSum , verifique si sum – temp existe en el vector creado anteriormente (después de ordenarlo ) usando la búsqueda binaria.
A continuación se muestra la implementación del enfoque anterior:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of the required quadruplets
int countQuadruplets(int arr1[], int n1, int arr2[],
int n2, int arr3[], int n3,
int arr4[], int n4, int value)
{
vector<int> sum1;
vector<int>::iterator it;
vector<int>::iterator it2;
int cnt = 0;
// Take every possible pair sum
// from the two arrays
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
// Push the sum to a vector
sum1.push_back(arr1[i] + arr2[j]);
}
}
// Sort the sum vector
sort(sum1.begin(), sum1.end());
// Calculate the pair sums from
// the other two arrays
for (int i = 0; i < n3; i++) {
for (int j = 0; j < n4; j++) {
// Calculate the sum
int temp = arr3[i] + arr4[j];
// Check whether temp can be added to any
// sum stored in the sum1 vector such that
// the result is the required sum
if (binary_search(sum1.begin(), sum1.end(), value - temp)) {
// Add the count of such values from the sum1 vector
it = lower_bound(sum1.begin(), sum1.end(), value - temp);
it2 = upper_bound(sum1.begin(), sum1.end(), value - temp);
cnt = cnt + ((it2 - sum1.begin()) - (it - sum1.begin()));
}
}
}
return cnt;
}
// Driver code
int main()
{
int arr1[] = { 0, 2 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = { -1, -2 };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int arr3[] = { 2, 1 };
int n3 = sizeof(arr3) / sizeof(arr3[0]);
int arr4[] = { 2, -1 };
int n4 = sizeof(arr4) / sizeof(arr4[0]);
int sum = 0;
cout << countQuadruplets(arr1, n1, arr2, n2,
arr3, n3, arr4, n4, sum);
return 0;
}
2
Publicación traducida automáticamente
Artículo escrito por everythingispossible y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA