1
$\begingroup$

Given a string $S$ which is a representation of a number in base $2$ i.e. a string of 0s and 1s, we need to find out the maximum possible value obtainable by erasing exactly one digit. The string's most significant digit is 1. This means $S$ represents a number greater than $0$.

I have a proof. If there is a more short and sweet proof please post it.

Let $S = aXYb$ where, $X$, $Y$ are single digits and $a$, $b$ are the bits to left of $X$ and to right of $Y$ respectively.

Then two important observations.

a. If $X$ = $Y$, we will obtain the same value aXb whether we remove X or Y.

b. We can then represent String S as a sequence of alternating groups of 1's and 0's i.e.

  1. $S = 11..100...011..100...0$, if $S$ ends in zero

  2. $S = 11..100...011..1$, if $S$ ends in one.

Within each group of 1's or 0's, we can remove any of digits of the same digit group and obtain same final value as obtained from observation above. Now, if $N = length(S)$, then our result is of length $N - 1$. We proceed fromthe $(N-1)$th bit(MSB) to the 1st bit(LSB) of resultant string and see if we can set the $i^{th}$ bit. We can have MSB of final result as 1 as the MSB of $S$ is 1. Using similar logic, we won't remove any of digits from the leftmost 1 digit group of $S$. Now consider the next digit of resultant string. We can place a 1 there only if the leftmost 0s group of $S$ is of length 1 since we can remove only one digit. Otherwise, we we will have the bit set to 0. To see that, we can write $S$ as $S = 1...10..01X$. To obtain maximum value, it is easy to see that we need to bring 1 (adjacent to X) to the left. Thus we need to remove a 0 from the lefmost 0 group.

I want to improve my discrete mathematics thinking. Thank you.

$\endgroup$
  • $\begingroup$ What does erasing a digit mean? Replacing by zero? $\endgroup$ – copper.hat Nov 2 '15 at 18:05
  • $\begingroup$ Let $S=aXb$. Then erasing digit $X$ means resulting string = $ab$. We need to find the lexicographically largest resultant string. $\endgroup$ – nitrogen Nov 2 '15 at 18:08
2
$\begingroup$

It’s essentially the same argument, but presented a bit more elegantly.

Suppose that the bit string is $\sigma=1b_1b_2\ldots b_n$. For $k=1,\ldots,n$ let $\sigma_k$ be the bit string that remains when $b_k$ is deleted, and let $\lambda_k$ be the substring of $\sigma$ to the left of $b_k$.

  • If $b_k=b_{k+1}$, clearly $\sigma_k=\sigma_{k+1}$.

  • If $b_k=0$, $b_{k+1}=1$, and $k<\ell$, the first $k+1$ bits of $\sigma_k$ are $\lambda_k1$, while the first $k+1$ bits of $\sigma_\ell$ are $\lambda_k0$, so $\sigma_k>\sigma_\ell$, where the order may be thought of either as lexicographic order or as the ordinary numerical order of the integers represented in binary by the bit strings.

  • Similarly, if $b_k=1$, $b_{k+1}=0$, and $k<\ell$, the first $k+1$ bits of $\sigma_k$ are $\lambda_k0$, while the first $k+1$ bits of $\sigma_\ell$ are $\lambda_k1$, so $\sigma_k<\sigma_\ell$.

Clearly if all bits of $\sigma$ are $1$, it makes no difference which we remove. Now suppose that $\sigma$ has a zero bit, and let $b_k$ be the leftmost zero bit. The first two points combined show that $\sigma_k\ge\sigma_\ell$ for all $\ell>k$, and the third shows that $\sigma_k>\sigma_\ell$ for all $\ell<k$, so removing the first zero maximizes the resulting string.

$\endgroup$
  • $\begingroup$ I wish I was able to write such proofs. Such proofs help in thinking very much. You can see that I was not able to express my proof clearly. I think I need more practice. $\endgroup$ – nitrogen Nov 2 '15 at 21:39
  • $\begingroup$ I have got so many problems that I need to express in such a way(but haven't been able to). Some problems are pretty daunting, especially problems employing greedy strategy. $\endgroup$ – nitrogen Nov 2 '15 at 21:42
  • $\begingroup$ @nitrogen: Practice does make a difference: you get to recognize certain patterns, just as you get to recognize patterns of reasoning when you solve a lot of problems. One thing that may help: whenever your argument involves an and so on step, try to find a way to convert that to a recursive construction or a proof by induction. $\endgroup$ – Brian M. Scott Nov 2 '15 at 21:44
  • $\begingroup$ I wish there were teachers like you and people around here at my place. I would try to gain as much as I possibly could. $\endgroup$ – nitrogen Nov 2 '15 at 21:46

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.