Encuentre cuatrillizos lexicográficamente crecientes únicos con suma como B y GCD de valores absolutos de todos los elementos es 1

Dada una array A de tamaño N y un entero B, la tarea es encontrar todos los cuatrillizos únicos dispuestos en orden lexicográficamente creciente de modo que la suma de los elementos de cada cuadruplicado sea B y el mcd de los valores absolutos de todos los elementos de un cuadriplicado es 1 .

Ejemplo :

Entrada: A = {1, 0, -1, 0, -2, 2 }, B = 0
Salida:
-2 -1 1 2
-1 0 0 1
Explicación: Solo hay tres cuatrillizos únicos que tienen suma = 0 que son {{-2, 0, 0, 2}, {-2, -1, 1, 2}, {-1, 0, 0, 1}} y de estos cuatrillizos solo el segundo y el tercero cuadruplicados tienen mcd igual a 1

Entrada: A = { 1, 5, 1, 0, 6, 0 }, B = 7
Salida:
0 0 1 6
0 1 1 5

Enfoque: la idea es almacenar la suma de cada par de elementos en un hashmap , luego iterar a través de todos los pares de elementos y luego buscar en el hashmap para encontrar pares tales que la suma del cuadruplicado sea igual a B y el gcd de valores absolutos de todos los elementos del cuadruplicado es igual a 1 . El enfoque detallado usando hashmap ha sido discutido en este artículo. Siga los pasos para resolver el problema.

• Inserte la suma de cada par de elementos de la array en un hashmap mp.
• Inicialice un punto fijo para almacenar todos los cuatrillizos.
• Atraviesa la array de i = 0 a N-1
  • Atraviesa la array de j = i+1 a N-1
    • Encuentre todos los pares del hashmap cuya suma sea igual a B-A[i]-A[j]. Inicializar un vector de pares v a mp[BA[i]-A[j]]. 
    • Recorre el vector v usando una variable k
      • Si v[k].primero o v[k].segundo es igual a i o j , continúe con la siguiente iteración.
      • Almacene los elementos del cuadruplicado en una array temporal . Ordenar la array temporal . Si el mcd de todos los elementos de la array temporal es 1, inserte la array temporal en st.
• Atraviese el punto establecido e imprima todos los cuatrillizos.

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all
// quadruplets with sum B.
void find4Sum(int A[], int N, int B)
{
    // Hashmap to store sum
    // of all pairs
    unordered_map<int,
                  vector<pair<int, int> > >
        mp;
 
    // Set to store all quadruplets
    set<vector<int> > st;
 
    // Traverse the array
    for (int i = 0; i < N - 1; i++) {
        // Traverse the array
        for (int j = i + 1; j < N; j++) {
            int sum = A[i] + A[j];
            // Insert sum of
            // current pair into
            // the hashmap
            mp[sum].push_back({ i, j });
        }
    }
 
    // Traverse the array
    for (int i = 0; i < N - 1; i++) {
        // Traverse the array
        for (int j = i + 1; j < N; j++) {
            int sum = A[i] + A[j];
            // Lookup the hashmap
            if (mp.find(B - sum) != mp.end()) {
                vector<pair<int, int> > v
                    = mp[B - sum];
 
                for (int k = 0; k < v.size(); k++) {
 
                    pair<int, int> it = v[k];
                    if (it.first != i && it.second != i
                        && it.first != j
                        && it.second != j) {
                        vector<int> temp;
                        temp.push_back(A[i]);
                        temp.push_back(A[j]);
                        temp.push_back(A[it.first]);
                        temp.push_back(A[it.second]);
 
                        // Stores the gcd of the
                        // quadrupled
                        int gc = abs(temp[0]);
                        gc = __gcd(abs(temp[1]), gc);
                        gc = __gcd(abs(temp[2]), gc);
                        gc = __gcd(abs(temp[3]), gc);
                        // Arrange in
                        // ascending order
                        sort(temp.begin(), temp.end());
                        // Insert into set if gcd is 1
                        if (gc == 1)
                            st.insert(temp);
                    }
                }
            }
        }
    }
    // Iterate through set
    for (auto it = st.begin(); it != st.end(); it++) {
        vector<int> temp = *it;
        // Print the elements
        for (int i = 0; i < 4; i++) {
            cout << temp[i] << " ";
        }
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Input
    int N = 6;
    int A[6]
        = { 1, 0, -1, 0, -2, 2 };
    int B = 0;
 
    // Function Call
    find4Sum(A, N, B);
    return 0;
}

# Python3 code for the above approach
from math import gcd
 
# Function to find all
# quadruplets with sum B.
def find4Sum( A, N, B):
   
    # Hashmap to store sum
    # of all pairs
    mp = dict()
     
    # Set to store all quadruplets
    st = set()
 
    # Traverse the array
    for i in range(N - 1):
        for j in range(i + 1, N):
            sum = A[i] + A[j]
             
            # Insert sum of
            # current pair into
            # the hashmap
            if sum not in mp:
                mp[sum] = []
            mp[sum].append([ i, j ])
         
 
    # Traverse the array
    for i in range(N - 1):
        # Traverse the array
        for j in range(i + 1, N):
             
            sum = A[i] + A[j]
            # Lookup the hashmap
            if (B - sum) in mp:
                v = mp[B - sum]
                 
                for k in range(len(v)):
                    it = v[k]
                    if it[0] != i and it[1] != i and it[0] != j and it[1] != j:
                        temp = (A[i], A[j], A[it[0]], A[it[1]])
 
                        # Stores the gcd of the
                        # quadrupled
                        gc = abs(temp[0]);
                        gc = gcd(abs(temp[1]), gc);
                        gc = gcd(abs(temp[2]), gc);
                        gc = gcd(abs(temp[3]), gc);
                         
                        # Arrange in
                        # ascending order
 
                        # Insert into set if gcd is 1
                        if (gc == 1):
                            st.add(tuple(sorted(temp)))
                             
    # Iterate through set
    for it in st:
        temp = it;
         
        # Print the elements
        print(*it)
 
# Driver Code
 
# Input
N = 6;
A = [ 1, 0, -1, 0, -2, 2 ];
B = 0;
 
# Function Call
find4Sum(A, N, B);
 
# This code is contributed by phasing17

-2 -1 1 2 
-1 0 0 1 

Complejidad de tiempo : O(N^3)
Espacio auxiliar: O(N^2)