# 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.
```

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 ` `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

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.