A Plus B

Interview

Time limit1sMemory limit1024 MB

Summary

Given two sorted arrays A and B of length N, output the N smallest of all N^2 pairwise sums A[i] + B[j] in increasing order.

Level: Medium5 of 10
Topics: Heap, Sorting
Solved: No attempts yet

Problem

Borcsa has two arrays, each containing $N$ non-negative integers. The first array holds $A[0], A[1], \dots, A[N-1]$ , and the second holds $B[0], B[1], \dots, B[N-1]$ . Both arrays are sorted in increasing order:

$A[0] ≤ A[1] ≤ \dots ≤ A[N-1]$
$B[0] ≤ B[1] ≤ \dots ≤ B[N-1]$

Borcsa computed the sum $A[i] + B[j]$ for every pair of indices $i$ and $j$ from $0$ to $N-1$ . Let $C$ be the list of all $N^2$ sums, sorted in increasing order. Find the first $N$ values of $C$ .

Constraints

$1 ≤ N ≤ 100{,}000$
$0 ≤ A[i] ≤ 10^9$ for each $i$ with $0 ≤ i < N$
$0 ≤ B[i] ≤ 10^9$ for each $i$ with $0 ≤ i < N$
$A$ and $B$ are sorted in increasing order.

Examples1

Example 1
Input
```
1
0
0
```
Expected output
```
0
```