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?”
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.