#### oppositeSums from Code Signal, possible O(n) solution?

[enter image description here] : https://i.stack.imgur.com/ZpHMn.png emphasized text

I was unable to solve this problem under O(N^2) time during my online assesment, it feels like in order to solve this problem, I have to check every pair possible due to edge cases such as [32, 332, 100] where 332 + 1 == 100 + 233. Can anyone lead me to a better solution?

Here’s my naive solution (exceeded time limit)

``````long long oppositeSums(std::vector<int> arr) {
long long result = 0;
vector<int> arr2(arr.size(), 0);
for (int i = 0; i < arr.size(); i++) {
arr2[i] = reverse(arr[i]);
}
for (int i = 0; i < arr.size(); i++) {
for (int j = i; j < arr.size(); j++) {
if (arr[i] + arr2[j] == arr[j] + arr2[i]) {
result++;
}
}
}

return result;
``````

}

Source: Windows Questions C++

## One Reply to “oppositeSums from Code Signal, possible O(n) solution?”

• KurlisLUL says:

Got this one in codesignal as well, luckily I could solve it, but lost too much time

I do not know if you are still looking for a solution but maybe someone else will do.

The important idea behind this one is that you have to think of it as an equality of:

value-reverse(value)=value2-reverse(value2)

You can now use a hashmap, to store the occurences of each [value-reverse(value)] value

Then iterate through the array elements again and get the occurences. Decrease the number the key occurs by one.