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.
$S = 11..100...011..100...0$, if $S$ ends in zero
$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.