0
$\begingroup$

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.

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

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 $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy