Find N’th item in a set formed by sum of two arrays
Given two sorted arrays, we can get a set of sums(add one element from the first and one from second). Find the N’th element in the elements of the formed set considered in sorted order.
Note: Set of sums should have unique elements.
Examples:
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.
Asked in: Microsoft Interview
Approach:
- Run two loops – one for the first array and second for the second array.
- Just consider each pair and store their sum in a self-balancing-BST (which is implemented by set and map in C++).
- We use set in C++ here as we need to only see if elements are present or absent, we don’t need key, value pairs.
- Traverse the set and return the Nth element in the set.
Below is the implementation of the above approach:
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> |
Output
N'th element in the set of sums is 6
Time Complexity: O(mn log (mn)) where m is the size of the first array and n is the size of the second array.
Contact Us