Baekjoon - Combining Two Solutions

Leetcode : Combining Two Solutions

Description

PH Solution's PH value is represented in positive integer ranging from 1 - 1,000,000,000. While the Alkaline solution's Alkaline value is represented in negative integer ranging from -1,000,000,000 to -1.
Return the value of numbers which the combination of the two values is closest to 0.

Examples

Input

5 // Number of Solutions
-2 4 -99 -1 98

Output

-99 98

Apporoach

Instead of using brute-force technique (i.e. - O(N^2)) to find the closest-to-zero value, using two-pointers algorithm will achieve the O(N) time complexity

Solutions

#include <iostream>
#include <algorithm>
using namespace std;

int N, sol[100001], ans[2];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> sol[i];
    }

	sort(sol, sol + N);

	int l = 0, r = N - 1, mn = 2000000000;

	while(l < r){
		int sum = sol[l] + sol[r];
		int tmp = abs(sum);
		if (mn > tmp) ans[0] = sol[l], ans[1] = sol[r], mn = tmp;
		if (!sum) break;
		sum > 0 ? --r : ++l;
	}

	cout << ans[0] << ' ' << ans[1];

	return 0;
}