# Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one.

A greedy algorithm for this would keep removing digits such that the resulting integer is the smallest. For the above example:

Step 1: Remove 2 => 114532
Step 2: Remove 5 => 11432
Step 3: Remove 4 => 1132
Step 4: Remove 3 => 112

Can you prove that this algorithm is optimal (i.e. the final integer is the smallest possible)? Or if it is not, show a counterexample?

Thanks!

• Have you tried proving that the algorithm is optimal? Do you know how these proofs go? Have you encountered any difficulties? – Yuval Filmus Jul 22 '19 at 16:46
• I was attempting to prove it by using the exchange-argument mechanism, showing that the greedy algorithm always stays ahead. But, can't seem to be able to think of an appropriate metric to show that it stays ahead. – nepee Jul 22 '19 at 17:04

The greedy algorithm is optimal.

The simple observation is that any optimal $$k$$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents.

Given an $$n$$-digit number $$A=a_{n-1}a_{n-2}\cdots a_1a_0$$, where each $$a_i$$ is a digit, let $$a_t$$ be the rightmost digit of $$A$$ such that $$a_n, a_{n-1}, \cdots, a_t$$ is non-decreasing. Let $$r$$ be the number of all digits that are equal to $$a_t$$ from $$a_t$$ to its left. In other words, the digits of $$A$$ are classified as displayed in the following illustration for some integer $$t$$ and $$r$$, where $$a_t>a_{t-1}$$ and $$a_{t+r}. Note that if there is only one digit in $$A$$, it is $$a_t$$ with $$t=0$$ and $$n=r=1$$. \begin{aligned} A&=\overbrace{a_{n-1}a_{n-2}\cdots a_{t+r}\ \underbrace{a_{t+r-1}\cdots a_{t+1}a_t}_{r\text{ copies of }a_t}}^{\text{longest non-decreasing}}\ a_{t-1}\cdots a_0\\ \mu(A)&=a_{n-1}a_{n-2}\cdots a_{t+r}\{r\text{-}1\text{ copies of }a_t\}a_{t-1}\cdots a_0\\ \end{aligned}

Define integer $$\mu(A)$$ as shown above, which is $$A$$ but with one of $$a_{t+r-1},\cdots,a_{t+1}, a_t$$ removed. For example, $$\mu(1214532)=114532$$, $$\mu(112)=11$$, $$\mu(40012)=0012$$ and $$\mu(0012)=001$$. Note that the value of $$\mu(A)$$ does not depend on the number of leading $$0$$'s in $$A$$. For example, $$\mu(001332)=00132{}=\mu(1332)=132$$.

Lemma. $$\mu(A)$$ is the smallest number that is $$A$$ with one digit removed.
Proof. Easy.

Let $$G$$ be the greedy algorithm. The lemma above says $$G(A,k)=\mu^k(A)$$.

Claim. For all non-negative integer pairs $$(A,k)$$, $$G$$ is optimal, i.e., $$G$$ returns the smallest number.
Proof. Let $$P(k)$$ be the proposition that $$G(I,k)$$ will return the smallest number for all integer $$I$$ of more than $$k$$ digits. The claim is $$P(0)$$, $$P(1)$$, $$P(2)$$, $$\cdots$$ are true.

Use induction on $$k$$. The base case, when $$k=0$$, is trivially true.

Assume $$P(k)$$, the induction hypothesis, is true. Let $$A$$ be an integer and $$S$$ be some $$k+1$$ digits of $$A$$ such that $$B$$, which is $$A$$ with digits in $$S$$ removed, is as small as possible. We will prove $$G(A,k+1)\le B$$, i.e, $$P(k+1)$$ is true, thus completing the induction.

Let us reuse the classification above of the digits of $$A$$, i.e., they start with the non-decreasing sequence $$a_{n-1}, a_{n-2}, \cdots, a_{t}$$ with $$a_{t}>a_{t-1}$$ and $$a_{t+r}.

• $$S$$ does not contain any digit in that sequence.

This cannot happen, since we can get a number smaller than $$B$$ by removing $$a_{t}$$ and arbitrary $$k-1$$ digits to the right of $$a_{t-1}$$.

• $$S$$ does contain one of the digits in that sequence, say, $$a_\ell$$.

• $$S$$ does not contain any one of $$a_{t+r-1}$$, $$\cdots$$, $$a_{t+1}$$, and $$a_t$$.

We can modify $$S$$ by substituting $$a_t$$ for $$a_\ell$$. The removal of the digits in the modified $$S$$ will return a number smaller than $$B$$. So this case cannot happen, either.

• Otherwise, WLOG, let $$a_\ell$$ be one of $$a_{t+r-1}$$, $$\cdots$$, $$a_{t+1}$$, and $$a_t$$.

The lemma above tells us that $$A$$ with $$a_\ell$$ removed is $$\mu(A)$$. Let $$S_-$$ be $$S$$ without $$a_\ell$$. So $$S_-$$ are some $$k$$ digits of $$\mu(A)$$. We have the following diagram, where the arrow reads "become". $$\require{AMScd}$$ $$\begin{CD} \mu(A),k@>\text{greedy algorithm}>> G(\mu(A), k)\\ @| \\ \mu(A),k@>{\text {remove elements in }S_-}>> B\\ \end{CD}$$

The induction hypothesis ensures $$G(\mu(A), k)\le B$$. Since $$G(A,k+1)=G(\mu(A), k)$$, we are done.

Exercise. (A couple of minutes or more) Given two positive integers $$k\lt n$$ and an $$n$$-digit integer $$A>0$$, how can you remove $$k$$ digits from $$A$$ such that the resulting integer is the biggest one? Explain the greedy algorithm. Prove it is correct.

The exercise shows that the greedy algorithm is still optimal in the original problem when $$A$$ is negative.

• Thanks for the update. I am a bit lost at the final line: "The induction hypothesis says G(Ω(A),k−1)≤B. Since G(A,k)=G(Ω(A),k−1), we are done." How did you prove G(Ω(A),k−1)≤B? – nepee Jul 25 '19 at 1:54
• I think a comma is needed here: "Assume 𝑃(𝑘), the induction hypothesis, is true" Got me confused for a while. And thanks for this. – nepee Jul 26 '19 at 17:12
• So, let me paraphrase the proof: Any optimal algorithm to remove k+1 digits on A must remove the rightmost digit in the initial non-decreasing digits of A (digit a_t). The greedy algorithm also must remove a_t from A. Now, after that, both optimal and greedy algorithms are left with the same set of digits in A (A - a_t) and the need to remove k digits. The induction hypothesis is that the greedy algorithm gives optimal result while removing k digits, which means, the greedy algorithm to remove k+1 digits must be equivalent to the optimal algorithm. Did I miss anything? – nepee Jul 26 '19 at 17:49
• @nepee Yes, you have understood it correctly. By the way, thanks for the comment on comma. That definitely helps me. – John L. Jul 26 '19 at 17:52
• @nepee, minor correction on your understanding. An optimal algorithm must remove $a_t$ or one of its equivalents. Had there not been those equivalents, (for example, when all digits of $A$ are different,) the proof could have been much shorter and clearer. – John L. Jul 26 '19 at 18:00