Minimizing the number of characters required to write a set of numbers

100 Views Asked by At

Let $n$ be an integer, and $f(n)$ be the number of characters write $n$ in decimal number. Eg. $f(13) = 2$ while $f(-13) = 3$ since we need a an extra minus sign for the negative number. Given a set of positive integers $S$, $\sum_{n \in S}f(n)$ is the total number of characters required to write all the numbers of $S$. Eg. If $S = \{3, 4, 9, 10, 12, 19, 102 \}$, then $\sum_{n \in S}f(n) = 12$.

In the above example, if we subtract $3$ from all numbers in $S$ we get a new set If $S_3 = \{0, 1, 6, 7, 9, 16, 99 \}$, then $\sum_{n \in S_3}f(n) = 9$. On the other hand if we $4$ from each number in $S$, we get $S_4 = \{-1, 0, 5, 6, 8, 15, 98 \}$ and $\sum_{n \in S_4}f(n) = 10$. Thus subtracting $4$ results in a set that requires more characters to write because of the negative sign in $-1$.

Now consider a sufficiently large set where subtracting a suitable number $c$ leads to one or more negative numbers but this tradeoff results in minimization of $\sum_{n \in S_c}f(n - c)$. Trivially $c \ge min(S)$.

Question 1: Let $S$ be a set of positive integers in $[a,b]$. How can we find a integer $c$ such that the sum $\sum_{n \in S_c}f(n - c)$ is minimum?

Question 2: Can we do better than $c = min(S)$ if the distribution of the numbers in $S$ is known say the numbers are approximately normally distributed in $[a,b]$ or has a left/right skew?