Encuentre el elemento N’th en un conjunto formado por la suma de dos arrays

Dadas dos arrays ordenadas, podemos obtener un conjunto de sumas (agregue un elemento del primero y otro del segundo). Encuentre el elemento N en los elementos del conjunto formado considerados en orden ordenado.

Nota: el conjunto de sumas debe tener elementos únicos.

Ejemplos: 

Input: arr1[] = {1, 2}
        arr2[] = {3, 4}
        N = 3
Output: 6
We get following elements set of sums.
4(1+3), 5(2+3 or 1+4), 6(2+4)
Third element in above set is 6.

Input: arr1[] = { 1,3, 4, 8, 10} 
        arr2[] = {20, 22, 30, 40} 
        N = 4
Output: 25
We get following elements set of sums.
21(1+20), 23(1+22 or 20+3), 24(20+4), 25(22+3)...
Fourth element is 25.

Preguntado en: Entrevista de Microsoft

Acercarse:

• Ejecute dos bucles: uno para la primera array y el segundo para la segunda array.
• Simplemente considere cada par y almacene su suma en un BST de autoequilibrio (que se implementa mediante el conjunto y el mapa en C++).
• Usamos set en C++ aquí, ya que solo necesitamos ver si los elementos están presentes o ausentes, no necesitamos pares clave, valor.
• Atraviesa el conjunto y devuelve el N-ésimo elemento del conjunto.

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

// C++ program to find N'th element in a set formed
// by sum of two arrays
#include<bits/stdc++.h>
using namespace std;
 
//Function to calculate the set of sums
int calculateSetOfSum(int arr1[], int size1, int arr2[],
                      int size2, int N)
{
    // Insert each pair sum into set. Note that a set
    // stores elements in sorted order and unique elements
    set<int> s;
    for (int i=0 ; i < size1; i++)
        for (int j=0; j < size2; j++)
            s.insert(arr1[i]+arr2[j]);
 
    // If set has less than N elements
    if (s.size() < N)
       return -1;
 
    // Find N'tb item in set and return it
    set<int>::iterator it = s.begin();
    for (int count=1; count<N; count++)
        it++;
    return *it;
}
 
// Driver code
int main()
{
    int arr1[] = {1, 2};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int arr2[] = {3, 4};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
 
    int N = 3;
    int res = calculateSetOfSum(arr1, size1, arr2, size2, N);
    if (res == -1)
        cout << "N'th term doesn't exists in set";
    else
        cout << "N'th element in the set of sums is "
             << res;
    return 0;
}

// Java program to find N'th element in a set formed
// by sum of two arrays
import java.util.*;
 
class GFG
{
 
// Function to calculate the set of sums
static int calculateSetOfSum(int arr1[], int size1, int arr2[],
                                            int size2, int N)
{
    // Insert each pair sum into set. Note that a set
    // stores elements in sorted order and unique elements
    SortedSet<Integer> s = new TreeSet<Integer>();
    for (int i = 0; i < size1; i++)
        for (int j = 0; j < size2; j++)
            s.add(arr1[i]+arr2[j]);
 
    // If set has less than N elements
    if (s.size() < N)
    return -1;
 
    // Find N'tb item in set and return it
     
    return (int)s.toArray()[ N-1 ];
}
 
// Driver code
public static void main(String[] args)
{
    int arr1[] = {1, 2};
    int size1 = arr1.length;
    int arr2[] = {3, 4};
    int size2 = arr2.length;
 
    int N = 3;
    int res = calculateSetOfSum(arr1, size1, arr2, size2, N);
    if (res == -1)
        System.out.println("N'th term doesn't exists in set");
    else
        System.out.println("N'th element in the set of sums is "
            +res);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find N'th
# element in a set formed
# by sum of two arrays
 
# Function to calculate the set of sums
def calculateSetOfSum(arr1, size1,arr2, size2, N):
     
    # Insert each pair sum into set.
    # Note that a set stores elements
    # in sorted order and unique elements
    s = set()
    for i in range(size1):
        for j in range(size2):
            s.add(arr1[i]+arr2[j])
 
    # If set has less than N elements
    if (len(s) < N):
        return -1
 
    # Find N'tb item in set and return it
    return list(s)[N - 1]
 
# Driver code
arr1 = [ 1, 2 ]
size1 = len(arr1)
arr2 = [ 3, 4 ]
size2 = len(arr2)
N = 3
 
res = calculateSetOfSum(arr1, size1,
                            arr2, size2, N)
if (res == -1):
    print("N'th term doesn't exists in set")
else:
    print(f"N'th element in the set of sums is {res}")
 
 
# This code is contributed by shinjanpatra

// C# program to find N'th element in
// a set formed by sum of two arrays
using System;
using System.Linq;
using System.Collections.Generic;
     
class GFG
{
 
// Function to calculate the set of sums
static int calculateSetOfSum(int []arr1, int size1,
                             int []arr2, int size2,
                             int N)
{
    // Insert each pair sum into set.
    // Note that a set stores elements in
    // sorted order and unique elements
    HashSet<int> s = new HashSet<int>();
    for (int i = 0; i < size1; i++)
        for (int j = 0; j < size2; j++)
            s.Add(arr1[i] + arr2[j]);
 
    // If set has less than N elements
    if (s.Count < N)
    return -1;
 
    // Find N'tb item in set and return it
    int []last = s.ToArray();
    return last[s.Count - 1];
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr1 = {1, 2};
    int size1 = arr1.Length;
    int []arr2 = {3, 4};
    int size2 = arr2.Length;
 
    int N = 3;
    int res = calculateSetOfSum(arr1, size1,
                                arr2, size2, N);
    if (res == -1)
        Console.WriteLine("N'th term doesn't exists in set");
    else
        Console.WriteLine("N'th element in the set" +
                               " of sums is " + res);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to find N'th
// element in a set formed
// by sum of two arrays
 
// Function to calculate the set of sums
function calculateSetOfSum(arr1, size1,
                           arr2, size2, N)
{
     
    // Insert each pair sum into set.
    // Note that a set stores elements
    // in sorted order and unique elements
    let s = new Set();
    for(let i = 0; i < size1; i++)
        for(let j = 0; j < size2; j++)
            s.add(arr1[i]+arr2[j]);
  
    // If set has less than N elements
    if (s.size < N)
        return -1;
  
    // Find N'tb item in set and return it
    return Array.from(s)[N - 1];
}
 
// Driver code
let arr1 = [ 1, 2 ];
let size1 = arr1.length;
let arr2 = [ 3, 4 ];
let size2 = arr2.length;
let N = 3;
 
let res = calculateSetOfSum(arr1, size1,
                            arr2, size2, N);
if (res == -1)
    document.write("N'th term doesn't " +
                   "exists in set");
else
    document.write("N'th element in the set " +
                   "of sums is " + res);
 
// This code is contributed by rag2127
 
</script>

N'th element in the set of sums is 6

Complejidad de tiempo: O(mn log (mn)) donde m es el tamaño de la primera array y n es el tamaño de la segunda array.

Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.