1
$\begingroup$

Given a number of N-digits A, I want to find the next least N-digit number B having the same sum of digits as A, if such a number exists. The original number A can start with a 0. For ex: A-> 111 then B-> 120, A->09999 B-> 18999, A->999 then B-> doesn't exist.

$\endgroup$
1
$\begingroup$

You get the required number by adding $9$, $90$, $900$ etc to $A$, depending on the digits of $A$.

First Case If $A$ does not end in a row of $9$s find the first (starting at the units end) non-zero digit. Write a $9$ under that digit and $0$s under all digits to the right of it. Add the two and you get $B$.

Example: $A=3450$. The first non-zero digit is the 5 so we write a $9$ under that and a $0$ to its right and add:
\begin{align} 3450\\ 90\\ \hline 3540 \end{align}

There is a problem if the digit to the left of the chosen non-zero digit is a $9$. In this case we write a $9$ under that $9$ and $0$s to its right. And if there are several $9$ we put our $9$ under the highest one.

Example: $A=3950$. The first non-zero digit is the 5 but there is a $9$ to its left. We write a $9$ under that $9$ instead and $0$s to its right and add:
\begin{align} 3950\\ 900\\ \hline 4850 \end{align}

Second case If $A$ does end in a row of $9$s write a $9$ under the highest of the row of $9$s and $0$s under all digits to the right of it. Add the two and you get $B$. As you say, if $A$ is entirely $9$s there is no solution.

Example: $A=3999$. The highest $9$ is in the hundreds column so we write a $9$ under that and $9$s to its right and add:
\begin{align} 3999\\ 900\\ \hline 4899 \end{align}

Edit This method does not always give the correct result. I will try and fix it in due course.
Edit 2 I have corrected my method and posted it in a new answer, so that this question's comment remain relevant.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Actually the second case is covered within the first case. But more importantly are you sure that this will cover all cases? $\endgroup$ – Siva Bathula Jun 19 '13 at 18:43
  • $\begingroup$ There are more instances of $A$s that don't have a $B$, for example $91, 92, \cdots, 98$ where a leading $0$ is required for the carry to work, for example $A=091 \implies B=181$. Other than these (and their multi-digit equivalents) I think all cases are covered. $\endgroup$ – Peter Phipps Jun 19 '13 at 19:10
  • $\begingroup$ Another instance where a leading zero is required is when $A$ is a single digit followed by zeros. For example $A=500$ has no solution but $A=0500 \implies B=1400$. And the same again with leading $9$s: $A=9950$ has no solution but $A=09950 \implies B=18950$. $\endgroup$ – Peter Phipps Jun 19 '13 at 20:18
  • $\begingroup$ @Dsa, My method gives $197+90=287$ but I take your point. $\endgroup$ – Peter Phipps Jun 20 '13 at 10:06
2
$\begingroup$

Divide the number into four regions:
Region 1: Trailing zeros.
Region 2: The lowest digit not in Region 1.
Region 3: Consecutive $9$s starting with the digit above Region 2.
Region 4: All remaining digits.

Region 1 and Region 3 may be empty. Region 4 may also be empty: if it is assume that it has value 0.

The required number is made up from bolting together the values $$\text{Region 4} + 1\quad\text{Region 1} \quad\text{Region 2} - 1 \quad\text{Region 3.}$$ It is obvious that the number of digits is the same because the $1$ added to Region 4 is cancelled out by the $1$ subtracted from Region 2 and all the other digits are the same, if in a different order.

Example 1: $217$ has no Region 1 or Region 3, Region 2 is $7$ and Region 4 is $21$. The required number is made up from $21+1$ and $7-1$, or $226$.

Example 2: $197$ has no Region 1, Region 2 is $7$, Region 3 is $9$ and Region 4 is $1$. The required number is made up from $1+1$ and $7-1$ and $9$, or $269$.

Example 3: $97$ has no Region 1, Region 2 is $7$, Region 3 is $9$ and Region 4 is empty so is assigned $0$. The required number is made up from $0+1$ and $7-1$ and $9$, or $169$.

Example 4: $199$ has no Region 1, Region 2 is $9$, Region 3 is $9$ and Region 4 is $1$. The required number is made up from $1+1$ and $9-1$ and $9$, or $289$.

Example 5: $468992000$ Region 1 is $000$, Region 2 is $2$, Region 3 is $99$ and Region 4 is $468$. The required number is made up from $468+1$ and $000$ and and $2-1$ and $99$, or $469000199$.

$\endgroup$
  • $\begingroup$ Can you please explain why this works? I need little intuition of the proof. $\endgroup$ – CodeLover Feb 1 '15 at 4:59
  • $\begingroup$ @CodeLover: The basic solution is to add $9$ to the lowest nonzero digit. In $37+9=46$, the sum of digits remains the same because the units digit decreases by $1$ but the tens digit gets a carry and increases by $1$. This is what's happening in my "Region 4 + 1" and "Region 2 - 1". It guarantees that the sum of digits remains the same. This method is OK unless there is one or more $9$ to the left of the lowest nonzero digit, as in $94+9=103$ which doesn't work. This is where Regions 1 and 3 come in. Region 1 contains only $0$s and Region 3 only $9$s. Just swapping them around doesn't (contd) $\endgroup$ – Peter Phipps Feb 1 '15 at 15:49
  • $\begingroup$ (contd) change the sum of their digits. Putting the $0$s after Region 4 and relegating the $9$s to the units end ensures that our number is as small as possible. I hope this helps. $\endgroup$ – Peter Phipps Feb 1 '15 at 15:50
  • $\begingroup$ Yes, thank you :) $\endgroup$ – CodeLover Feb 2 '15 at 5:59

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.