Tìm phần tử thứ N trong tập hợp tổng của hai mảng trong C++

Giới thiệu

Cho hai mảng đã sắp xếp arr1[], arr2[] kích thước m và số N. Tạo tập hợp các tổng arr1[i] + arr2[j]. Tìm phần tử thứ N của tập hợp (loại bỏ trùng lặp).

Ví dụ minh họa

Đầu vào

arr1[] = {3, 1, 5}, arr2[] = {6, 2, 8}, N = 4

Đầu ra

7

Giải thích

Các tổng duy nhất: 3(1+2), 5(3+2), 7(1+6,5+2), 9(3+6,1+8), 11(3+8,5+6), 13(5+8).
Phần tử thứ 4: 7

Phương pháp giải

Dùng lồng vòng for tính mọi tổng, lưu vào set để tự động loại trùng và sắp xếp. Duyệt set đến phần tử thứ N.

Chương trình minh họa

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int findNthSumElement(vector& arr1, vector& arr2, int N) {
    set sums;
    for (int x : arr1)
        for (int y : arr2)
            sums.insert(x + y);
    
    auto it = sums.begin();
    advance(it, N-1);
    return (it != sums.end()) ? *it : -1;
}

int main() {
    vector arr1 = {3, 1, 5};
    vector arr2 = {6, 2, 8};
    int N = 4;
    cout << "The " << N << "th element in sum set is " << findNthSumElement(arr1, arr2, N);
    return 0;
}

Đầu ra

The 4th element in sum set is 7

Lưu ý: Code mẫu trong nội dung gốc bị nhầm lẫn hoàn toàn với bài toán khác (giải hệ phương trình).