I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).
We have a rectangle of known dimensions where every value of column and row (zero-indexed) are XOR-ed in order to create a value. Then, we must compute the sum of every value of that rectangle. (i.e. for a rectange of 8 columns & 5 rows, the first value would be 0 ^ 0 = 0, then 0 ^ 1 = 1, etc. until 7 ^ 4 = 3, then the sum of every value would give 105, which is the result)
I've tried different approach to this problem, but every one of them end up being too slow and not enough efficient. The naive solution is of time complexity $O(N^2)$, which becomes too slow when we're working with a lot of values.
Here would be the function to compute the value of 1 row. (x is the number of columns & y is the number of the current row) $$ f(x,y) = (0 \oplus y) + (1 \oplus y) + (2 \oplus y) + (3 \oplus y) + .. + ((x - 1) \oplus y) $$ So the whole rectangle would be that function from 0 to y - 1 for the y value.
So my question is: Is there a way where I can simplify a function like that to gain efficiency ?