/
2 num. sum closest to 0.cpp
129 lines (89 loc) · 2.09 KB
/
2 num. sum closest to 0.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
///////////////////////////////////////////
//Question/Info
Two numbers with sum closest to zero
Medium Accuracy: 31.86% Submissions: 7260 Points: 4
Given an integer array of N elements. You need to find the maximum sum of two elements such that sum is closest to zero.
Example 1:
Input:
N = 3
arr[] = {-8 -66 -60}
Output: -68
Explanation: Sum of two elements closest to
zero is -68 using numbers -60 and -8.
​Example 2:
Input:
N = 6
arr[] = {-21 -67 -37 -18 4 -65}
Output: -14
Explanation: Sum of two elements closest to
zero is -14 using numbers -18 and 4.
Your Task:
You don't need to read input or print anything. You just need to complete the function closestToZero() which takes an array arr[] and its size n as inputs and returns the maximum sum closest to zero that can be formed by summing any two elements in the array.
Expected Time Complexity: O(N*logN).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 5 * 105
-106 ≤ arr[i] ≤ 106
Company Tags
Accolite Amazon Fab.com Microsoft Snapdeal
author: srj_v
///////////////////////////////////////////
*/
#include <bits/stdc++.h>
using namespace std;
#define _IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long double ld;
typedef long long int lli;
#pragma GCC optimize("Ofast")
void c_p_c()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int32_t main() {
///////////
c_p_c();
///////////
_IOS
//////////
// code
/*
int t ; cin >> t; while(t--){}
*/
class Solution
{
public:
int closestToZero(int arr[], int n)
{
sort(arr, arr + n);
int i = 0; int j = n - 1;
int res = INT_MIN; int flag = INT_MAX;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum == 0) {
return 0 ;
}
else if (sum < 0) {
i++;
}
else {
j--;
}
if (abs(sum) < flag) {
flag = abs(sum);
res = sum;
}
// NUM SUM. CLOSEST TO 0 ~ MAX CASE :
else if (abs(sum) == flag) {
res = max(res, sum);
}
}
return res;
}
};
// cerr << "time: " << clock() << " ms" << '\n';
return 0;
}