Anonymous user
Next highest int from digits: Difference between revisions
m
used gold section header for E.g., added whitespace, added whitespace before the TOC, corrected a misspelling.
m (used gold section header for E.g., added whitespace, added whitespace before the TOC, corrected a misspelling.) |
|||
Line 4:
integer using only the given digits<sup>*1</sup>.
* Numbers will not be padded to the left with zeroes.
* Use all given digits, with their given multiplicity. (If a digit appears twice in the input number, it should appear twice in the result).
* If there is no next
<br><sup>*1</sup> Alternatively phrased as: "Find the smallest integer larger than the (positive or zero) integer N which can be obtained by reordering the (base 10) digits of N".▼
▲<br><sup>*1</sup> Alternatively phrased as: "Find the smallest integer larger than the (positive or zero) integer N which can be obtained by reordering the (base 10) digits of N".
;Algorithm 1:
# Generate all the permutations of the digits and sort into numeric order.
# Find the number in the list.
# Return the next highest number from the list.
The above could prove slow and memory hungry for numbers with large numbers of
Line 20 ⟶ 22:
;Algorithm 2:
# Scan right-to-left through the digits of the number until you find a digit with a larger digit somewhere to the right of it.
# Exchange that digit with the digit on the right that is ''both'' more than it, and closest to it.
# Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. (I.e. so they form the lowest numerical representation)
'''E.g.:'''
<pre>
n = 12453
Line 38 ⟶ 41:
This second algorithm is faster and more memory efficient, but implementations
may be harder to test.
One method of testing, (as used in developing the task), is to compare results from both
algorithms for random numbers generated from a range that the first algorithm can handle.
;Task requirements:
Calculate the next highest int from the digits of the following numbers:
:* 0
:* 9
:* 12
:* 21
:* 12453
:* 738440
:* 45072010
:* 95322020
;Optional stretch goal:
:* 9589776899767587796600
<br><br>
=={{header|C}}==
| |||