0
$\begingroup$

I was doing problems in "Leetcode" and found a problem that I could not solve.

Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \leq b$ and among those find the maximum value of $n \& i$ where $\&$ means bitwise and.

I could only solve when $a=0$ by finding the most significant bit location in $b$ and in $n$ and comparing both and find that $i$ should be $b$ or let location of most significant bit be $k$ from right then it must be $1111111.......1$ $(k-1)$ times.

But when $a \neq 0$ I am struck. Can anybody help me?

P.S : I am finding the question and I will post it's link by tomorrow.

$\endgroup$
1
  • 2
    $\begingroup$ Where is the link to the original problem? Apparently, this is not a problem on Leetcode. $\endgroup$
    – John L.
    May 5 '20 at 2:08
1
$\begingroup$

Here is how to reduce this to the case you already know how to solve.

If $a = b$, there is nothing to do. Otherwise, the binary expansion of $a,b$ is of the form $a = x0\alpha$ and $b = x1\beta$, where $|\alpha| = |\beta|$. If the bit of $n$ corresponding to the differing bit of $a,b$ is $0$, then the corresponding bit of $i$ should be $1$, and vice versa (more significant bits are forced to $x$).

In the first case, we are looking for a solution in the range $x10^{|\beta|}$ to $b$, which reduces to $0^{|\beta|}$ to $b$; that you already know how to solve.

In the second case, we are looking for a solution in the range $x0\alpha$ to $x01^{\alpha}$, which reduces to $\alpha$ to $1^{|\alpha|}$; that should have a solution analogous to the case you're familiar with.

$\endgroup$
6
  • $\begingroup$ But i did not understand your binary expansion ,and what is menaing of $x$ and ,why $|\alpha|=|\beta|$ ? $\endgroup$
    – Sandeep
    May 4 '20 at 16:19
  • $\begingroup$ Perhaps an example will help. Let $a=9$ and $b=12$. Then the binary expansion of $a$ is $1001$, and that of $b$ is $1010$. In this case $x = 10$, $\alpha = 1$, $\beta = 0$. $\endgroup$ May 4 '20 at 16:36
  • $\begingroup$ It in answer it was mentioned that $|\alpha|=|\beta|$ $\endgroup$
    – Sandeep
    May 4 '20 at 16:39
  • 1
    $\begingroup$ Right: $|\alpha| = |\beta| = 1$. It's the length of $\alpha,\beta$ as bitstrings. $\endgroup$ May 4 '20 at 16:40
  • $\begingroup$ And also meaning of $x10^{|\beta|}$ , $\endgroup$
    – Sandeep
    May 4 '20 at 16:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.