Efficient algorithm to compare arrays problem

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 X[0] and Y[0] 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.

• Please credit the original source where you encountered this task. – D.W. May 9 at 21:35
• wasn't able to find a solution Please show where your efforts got you. – greybeard May 11 at 12:24

1 Answer

You can write $$x$$ and $$y$$ in binary as \begin{align} x&=x_{M-1} \ldots x_0 \\ y&=y_{M-1} \ldots y_0 \end{align} (This is exactly the contents of your arrays.) Since $$x \neq y$$, there must be a first bit (from the left) at which they differ. Say that this bit is $$x_i \neq y_i$$. Since $$y > x$$, we know that $$y_i = 1$$ and $$x_i = 0$$. Thus \begin{align} x &= x_{M-1} \ldots x_{i+1} 0 x_{i-1} \ldots x_0 \\ y &= x_{M-1} \ldots x_{i+1} 1 y_{i-1} \ldots y_0 \end{align} The following two integers are in the range $$x,\ldots,y$$: \begin{align} &x_{M-1} \ldots x_{i+1} 0 1 \ldots 1 \\ &x_{M-1} \ldots x_{i+1} 1 0 \ldots 0 \end{align} This shows that if you take the AND of all integers from $$x$$ to $$y$$, you get $$x_{M-1} \ldots x_{i+1} 0 0 \ldots 0$$