O(N) ^^
time:O(N); space: O(N)\n get three greatest numbers in the first array (M1 > M2 > M3 > ...);\n get greatest number of the second array G;\n* test x=G-M1 then x=
**time:`O(N)`; space: `O(N)`**\n* get three greatest numbers in the first array (`M1 > M2 > M3 > ...`);\n* get greatest number of the second array `G`;\n* test `x=G-M1` then `x=G-M2`. If both fail return `x=G-M3`;\n\n```\nclass Solution \n{\n    bool check(vector<int>& n1, vector<int>& n2, int M, int G)\n    {\n        unordered_map<int, int> um;\n        for(const auto & n : n1) ++um[n+G-M];\n        for(const auto & n : n2) --um[n];\n        return 2==accumulate(begin(um), end(um), 0, [](int s, auto e){ return s+abs(e.second); });\n    }\n    \npublic:\n    int minimumAddedInteger(vector<int>& n1, vector<int>& n2) \n    {\n        int M1{INT_MIN}, M2{M1}, M3{M1}, G{*max_element(begin(n2), end(n2))};\n        for(const auto & n : n1)\n            M3 = n>M1 ? exchange(M2, exchange(M1, n)) : n>M2 ? exchange(M2, n) : n>M3 ? n : M3;\n        return G - (check(n1, n2, M1, G) ? M1 : check(n1, n2, M2, G) ? M2 : M3);\n    }\n};\n```\n\n
['C', 'C++']