# Largest number with sum S and N number of digits

Given a number N and sum as S .What is the mathematical approach to construct the largest number having N digits whose sum is S and smallest number of N digits whose sum is again S. Leading zero digit numbers are not considered.

• Put the number 9 as the first digit and after the biggest one to fill the sum S, by example if S=19 and N=5 then the largest number is 99100. The smaller is the "reverse", start with 9 in the last digit and continue putting numbers and reserve a 1 to the first digit by example for the anterior case the smaller number is 10099. – Masacroso Mar 18 '16 at 14:34
• Any number with $N$ digits starting with 9 is bigger than any number with $N$ digits starting with a smaller digit. Note that there are no such numbers if $S>9N$. But we get the largest by taking $[S/N]$ 9s followed by one digit $S-9[S/N]$ followed by 0s. A similar approach for the smallest, except that there is an ambiguity for the smallest: is it allowed to begin with 0s? If not start it with a 1. – almagest Mar 18 '16 at 14:34

(a)Fill the first $\lfloor\frac S9 \rfloor$ digits by $9$
Fill the next digit by $S\mod9$
Fill the rest of the digits by $0$

(b)Fill the last $\lfloor\frac {S-1}9 \rfloor$ digits by $9$
Fill the previous digit by $S-1\mod9$
Fill the rest of the digits by $0$
Add $1$ to the first digit.

Example from the comment below, $S=15$, $N=2$

$\lfloor\frac {S-1}9 \rfloor = 1$

$S-1\mod9 = 5$

So, you have $59$. No remaining digits, so no $0$s. Now, the last step - add $1$ gives $69$

• can u illustrate b with an example – satyajeet jha Mar 18 '16 at 15:04
• if SUM is 15 and u have to make the smallest 2 digit number,ans is 69.By doing as per your method floor(15-1/9)=1 so i placed 9at last and for next digit i need 6 to make 69 but your method 15-1%9=5 ,so it goes wrong here.CORRECT me if my argument is wrong – satyajeet jha Mar 18 '16 at 15:19
• You are right. My method assuming certain things.. I just exchanged two steps in my method. Now, it will take care of that wrong assumption. Thank you. – Win Vineeth Mar 18 '16 at 15:33
• @Vin Vineeth where is the correct version ?YOU have not yet edited it . – satyajeet jha Mar 18 '16 at 15:41
• @satya I exchanged two steps in my method. Well, I edited it again to include your example. – Win Vineeth Mar 18 '16 at 15:43

I assume you mean a number with $N$ digits in decimal base and having the digit sum $S$.

It runs down to partition the number $S$ into $N$ parts (if possible at all!), where the parts are in the range $\{ 0, \dotsc, 9 \}$ and sorting it such that either the largest parts come first for a maximal number, or such that the smallest parts come first for a minimal number. Of all feasible partitions one picks the one which comes first under the considered order.

One could pose it as integer linear programming (ILP) problem, e.g. \begin{matrix} \max & c^\top x \\ \text{w.r.t.} & Ax = b \\ & 0 \le x \\ & x \le 9 \end{matrix} with \begin{align} c^\top &= (10^{N-1}, 10^{N-2}, \dotsc, 1) \in \mathbb{R}^{1 \times N} \\ A &= (1, \dotsc, 1) \in \mathbb{R}^{1 \times N} \\ x &= (x_!, \dotsc, x_N)^\top \in \mathbb{Z}^N \\ b &= (S) \in \mathbb{N} \end{align} and use a solver.

The minimal number is a bit trickier, because of the convention that leading $0$ digits are dropped (except for single digit numbers).