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++
// 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
// 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
# 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#
// 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
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA