I was submitted an interesting problem, but I wasn't able to find a solution.
Define a function
p(x, y) that takes int x and y, with
y > x and returns an int.
p(x, y) = x & (x+1) & (x+2) & ... & (y-1) & y
There are then two arrays X of length N and Y of length M representing x and y, in binary with
M >= N > 0. X and Y are consistently indexed, so that
Y represent the least significant digit of x and y.
The final goal is to write an efficient algorithm that computer
p(x, y). The ideal solution would be to have a time complexity of O(M) and a space complexity of O(M).
We can assume that the bitwise AND operator is already implemented with a complexity of O(M) in both time and space. There's also no need to work on the binary representation of the numbers. Pseudocode is fine.