-1

Given a number X and integer N, give the max value for (X&i) 0<=i<=N. Example: X = 103, N = 50 ans = 44

Bharat Arya
  • 3
  • 2
  • 3
    What have you tried? A greedy algorithm seems likely to work here. The proposed answer does not seem right. $44$ has the eight bit set and $103$ does not. I get $39$ – Ross Millikan May 06 '20 at 15:09

1 Answers1

1

If $N \geq X$, the simply return $X$.

If $N \leq X$, then start from the most-significant bit of $N$ (i.e. the left-most place value with a $1$). We will denote the bit we are examining as place value $b$, and also keep a value $A$ (which will be our answer). $A$ is initialized to zero. Then do the following loop (again, we start at the most significant bit of $N$):

  1. If the $b$ place value of $X$ is $x$ and the $b$ place value of $N$ is also $x$, then set the $b$ place value of $A$ to be $x$.

  2. If the $b$ place value of $X$ is $0$ and the $b$ place value of $N$ is $1$, then set the remaining (lesser significant bits) of $A$ to match the respective bits in $X$, and exit the loop.

The answer (i.e. the maximum value of $X ~ \& ~ i$) will be $A$ at the end.

paulinho
  • 6,553