Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

lucius_fox's blog

By lucius_fox, history, 15 months ago, In English

In C, how do you prove that if no character appears more than floor(n/2) times, we can always achieve n%2 length of the final string? (where 'n' is the length of the given string) Please help.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Let

  • n equal the current length of the string
  • maxf1 equal the current largest frequency of any character
  • maxf2 equal the current second largest frequency of any character.

First, notice that we can do some operation exactly when maxf1<n.

Case 1: n\equiv0\pmod{2}

Claim: If \mathrm{maxf}_1 \le n/2 and n > 0, we can do an operation such that after the operation, \mathrm{maxf}_1 \le n/2.

Proof:

  • If \mathrm{maxf}_1 < n/2, we can do any operation. After the operation n_{\mathrm{new}} = n-2 and n_{\mathrm{new}}/2 = (n-2)/2 = n/2-1 and because \mathrm{maxf}_1 < n/2, then \mathrm{maxf}_1 \le n/2-1 = n_{\mathrm{new}}/2.
  • If \mathrm{maxf}_1 = n/2 and \mathrm{maxf}_2 < n/2, we can do one operation which decreases \mathrm{maxf}_1 by one. Now \mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = n/2-1 = n_{\mathrm{new}}/2, meaning that \mathrm{maxf}_{1\mathrm{new}} \le n_{\mathrm{new}}/2. Similar to the previous case, \mathrm{maxf}_2 \le n/2-1 = n_{\mathrm{new}}/2.
  • If \mathrm{maxf}_1 = n/2 and \mathrm{maxf}_2 = n/2, we have \mathrm{maxf}_1 + \mathrm{maxf}_2 = n. This means that there are no other characters than those two, so we can delete one of each. Now \mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = \mathrm{maxf}_{2\mathrm{new}} = \mathrm{maxf}_2-1 = n/2-1 = n_{\mathrm{new}}/2, meaning that \mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_{2\mathrm{new}} \le n_{\mathrm{new}}/2.

This means that if we have \mathrm{maxf}_1 \le n/2 and \mathrm{maxf}_1 < n, we can do an operation and keep the first condition satisfied. Thus, we can do operations while n/2 < n\ \Leftrightarrow\ 0 < n/2\ \Leftrightarrow\ n > 0. Thus we can always reach the state with n = 0. \square

Case 2: n\equiv1\pmod{2}

Claim: If \mathrm{maxf}_1 \le \lceil n/2\rceil and n > 1, we can do an operation such that after the operation, \mathrm{maxf}_1 \le \lceil n/2\rceil.

Proof:

  • If \mathrm{maxf}_1 < \lceil n/2\rceil, we can do any operation. After the operation n_{\mathrm{new}} = n-2 and \lceil n_{\mathrm{new}}/2\rceil = (n_{\mathrm{new}}+1)/2 = (n-2+1)/2 = (n+1)/2 - 1 = \lceil n/2\rceil-1 and because \mathrm{maxf}_1 < \lceil n/2\rceil, then \mathrm{maxf}_1 \le \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil.
  • If \mathrm{maxf}_1 = \lceil n/2\rceil and \mathrm{maxf}_2 < \lceil n/2\rceil, we can do one operation which decreases \mathrm{maxf}_1 by one. Now \mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil, meaning that \mathrm{maxf}_{1\mathrm{new}} \le \lceil n_{\mathrm{new}}/2\rceil. Similar to the previous case, \mathrm{maxf}_2 \le \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil.
  • Notice that the case with \mathrm{maxf}_1 = \lceil n/2\rceil and \mathrm{maxf}_2 = \lceil n/2\rceil doesn't exist as \mathrm{maxf}_1 + \mathrm{maxf}_2 = 2\lceil n/2\rceil = 2(n+1)/2 = n+1 > n, which is not possible.

This means that if we have \mathrm{maxf}_1 \le \lceil n/2\rceil and \mathrm{maxf}_1 < n, we can do an operation and keep the first condition satisfied. Thus, we can do operations while \lceil n/2\rceil < n\ \Leftrightarrow\ (n+1)/2 < n\ \Leftrightarrow\ n+1 < 2n\ \Leftrightarrow\ 1 < 2n-n\ \Leftrightarrow\ n > 1. Thus we can always reach the state with n = 1. \square