3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Masacroso Mar 18 '16 at 14:34
  • $\begingroup$ 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. $\endgroup$ – almagest Mar 18 '16 at 14:34
2
$\begingroup$

(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$

$\endgroup$
  • $\begingroup$ can u illustrate b with an example $\endgroup$ – satyajeet jha Mar 18 '16 at 15:04
  • $\begingroup$ 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 $\endgroup$ – satyajeet jha Mar 18 '16 at 15:19
  • $\begingroup$ 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. $\endgroup$ – Win Vineeth Mar 18 '16 at 15:33
  • $\begingroup$ @Vin Vineeth where is the correct version ?YOU have not yet edited it . $\endgroup$ – satyajeet jha Mar 18 '16 at 15:41
  • $\begingroup$ @satya I exchanged two steps in my method. Well, I edited it again to include your example. $\endgroup$ – Win Vineeth Mar 18 '16 at 15:43
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.