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

1- Run two loops – one for first array and second for second array.

2- 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.

3- Traverse the set and return the Nth element in the set.

Below is C++ implementation of above idea.

`// 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; ` `} ` |

Output:

Nth element in the set of sums is 25

Time Complexity: O(mn log (mn)) where m is the size of the first array and n is the size of the second array.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments