Par de arrays con igual suma después de eliminar exactamente un elemento de cada

Dadas K arrays de diferente tamaño. La tarea es verificar si existen dos arreglos que tengan la misma suma de elementos después de eliminar exactamente un elemento de cada uno de ellos. (Se puede eliminar cualquier elemento, pero se debe eliminar exactamente uno ). Imprima los índices de la array y el índice de los elementos eliminados si existen tales pares. Si hay varios pares, imprima cualquiera de ellos. Si no existen tales pares, imprima -1.

Ejemplos:

Entrada: k = 3
a1 = {8, 1, 4, 7, 1}
a2 = {10, 10}
a3 = {1, 3, 4, 7, 3, 2, 2}
Salida: Array 1, índice 4
Array 3, índice 5
suma de Array 1{8, 1, 4, 7, 1} sin índice 4 es 20.
suma de Array 3{1, 3, 4, 7, 3, 2, 2} sin índice 5 es 20.

Entrada: k = 4
a1 = {2, 4, 6, 6}
a2 = {1, 2, 4, 8, 16}
a3 = {1, 3, 8}
a4 = {1, 4, 16, 64}
Salida : -1

Fuerza bruta:
para cada par de arrays, para cada elemento, encuentre la suma excluyendo ese elemento y compárela con la suma excluyendo cada elemento uno por uno en la segunda array del par elegido.
(Aquí maxl denota la longitud máxima de una array en el conjunto).

Complejidad de tiempo : $\mathcal{O}(k*k*maxl*maxl)$
Complejidad de espacio : $\mathcal{O}(k*maxl)$

Enfoque eficiente: precalcule todos los valores posibles de la suma obtenida al eliminar un elemento de cada una de las arrays. Almacene el índice de la array y el índice del elemento que se elimina con la suma calculada. Cuando estos valores se organizan en orden creciente, se puede ver fácilmente que si existe una solución, ambos valores de la suma deben ser adyacentes a la nueva disposición. Cuando dos valores de suma adyacentes son iguales, verifique si pertenecen a arrays diferentes. Si lo hacen, imprima el número de array y el índice del elemento eliminado. Si no se encuentra tal valor de suma, entonces no existen tales pares.

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

// C++program to print the pair of arrays
// whose sum are equal after removing
// exactly one element from each
#include <bits/stdc++.h>
using namespace std;
  
// Function to print the pair of array and index
// of element to be removed to make sum equal
void printPair(vector<int> a[], int k)
{
  
    // stores the sum removing one element,
    // array number and index of removed element
    vector<pair<int, pair<int, int> > > ans;
  
    // traverse in every array
    for (int i = 0; i < k; i++) {
  
        // length of array
        int l = a[i].size();
  
        int sum = 0;
  
        // compute total sum of array
        for (int j = 0; j < l; j++) {
            sum = sum + a[i][j];
        }
  
        // remove each element once and insert sum in
        // ans vector along with index
        for (int j = 0; j < l; j++) {
            ans.push_back({ sum - a[i][j], { i + 1, j } });
        }
    }
  
    // sort the ans vector so that
    // same sum values after removing
    // a single element comes together
    sort(ans.begin(), ans.end());
  
    bool flag = false;
  
    // iterate and check if any adjacent sum are equal
    for (int p = 1; p < ans.size(); p++) {
  
        // check if the adjacent sum belong to different array
        // if the adjacent sum is equal
        if (ans[p - 1].first == ans[p].first
            && ans[p - 1].second.first != ans[p].second.first) {
  
            // first array number
            int ax = ans[p - 1].second.first;
  
            // element's index removed from first array
            int aidx = ans[p - 1].second.second;
  
            // second  array number
            int bx = ans[p].second.first;
  
            // element's index removed from second array
            int bidx = ans[p].second.second;
  
            cout << "Array " << ax << ", index " << aidx << "\n";
            cout << "Array " << bx << ", index " << bidx << "\n";
  
            flag = true;
            break;
        }
    }
  
    // If no pairs are found
    if (!flag)
        cout << "No special pair exists\n";
}
  
// Driver Code
int main()
{
    // k sets of array
    vector<int> a[] = {
        { 8, 1, 4, 7, 1 },
        { 10, 10 },
        { 1, 3, 4, 7, 3, 2, 2 }
    };
    int k = sizeof(a) / sizeof(a[0]);
  
    // Calling Function to print the pairs if any
    printPair(a, k);
  
    return 0;
}

Producción:

Array 1, index 4
Array 3, index 5

Complejidad Temporal : $\mathcal{O}(\sum_{i=1}^{i=k}l_{i})$ , o simplemente, $\mathcal{O}(k*maxl)$
Complejidad Espacial : $\mathcal{O}(\sum_{i=1}^{i=k}l_{i})$ , o simplemente, $\mathcal{O}(k*maxl)$

Publicación traducida automáticamente

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

Deja una respuesta Cancelar la respuesta