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.
Asked
Active
Viewed 2,311 times
2 Answers
2
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$.
Peter Phipps
- 3,065
-
Can you please explain why this works? I need little intuition of the proof. – CodeLover Feb 01 '15 at 04:59
-
@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) – Peter Phipps Feb 01 '15 at 15:49
-
(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. – Peter Phipps Feb 01 '15 at 15:50
-
Yes, thank you :) – CodeLover Feb 02 '15 at 05:59
1
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.
Peter Phipps
- 3,065
-
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? – Siva Bathula Jun 19 '13 at 18:43
-
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. – Peter Phipps Jun 19 '13 at 19:10
-
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$. – Peter Phipps Jun 19 '13 at 20:18
-