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 &gt; x and returns an int.

p(x, y) = x &amp; (x+1) &amp; (x+2) &amp; ... &amp; (y-1) &amp; y

There are then two arrays X of length N and Y of length M representing x and y, in binary with M &gt;= N &gt; 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.
You can write $x$ and $y$ in binary as
\begin{align}
x&amp;=x_{M-1} \ldots x_0 \\
y&amp;=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 &gt; x$, we know that $y_i = 1$ and $x_i = 0$. Thus
\begin{align}
x &amp;= x_{M-1} \ldots x_{i+1} 0 x_{i-1} \ldots x_0 \\
y &amp;= 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}
&amp;x_{M-1} \ldots x_{i+1} 0 1 \ldots 1 \\
&amp;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
$$