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

  c++, dynamic-programming
[enter image description here][1] [1]: 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?”

  • 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.

LEAVE A COMMENT