Next highest int from digits: Difference between revisions

Content added Content deleted
m (used gold section header for E.g., added whitespace, added whitespace before the TOC, corrected a misspelling.)
Line 4: Line 4:
integer using only the given digits<sup>*1</sup>.
integer using only the given digits<sup>*1</sup>.


* Numbers will not be padded to the left with zeroes.
* &nbsp; 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).
* &nbsp; 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 higest integer return zero.
* &nbsp; If there is no next highest integer return zero.

⚫
<br><sup>*1</sup> &nbsp; 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:
;Algorithm 1:
# Generate all the permutations of the digits and sort into numeric order.
# &nbsp; Generate all the permutations of the digits and sort into numeric order.
# Find the number in the list.
# &nbsp; Find the number in the list.
# Return the next highest number from the list.
# &nbsp; Return the next highest number from the list.



The above could prove slow and memory hungry for numbers with large numbers of
The above could prove slow and memory hungry for numbers with large numbers of
Line 20: Line 22:


;Algorithm 2:
;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.
# &nbsp; 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.
# &nbsp; 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)
# &nbsp; 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:
'''E.g.:'''
<pre>
<pre>
n = 12453
n = 12453
Line 38: Line 41:


This second algorithm is faster and more memory efficient, but implementations
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),
may be harder to test.

is to compare results from both algorithms for random numbers generated from a
One method of testing, (as used in developing the task), &nbsp; is to compare results from both
range that the first algorithm can handle.
algorithms for random numbers generated from a range that the first algorithm can handle.




;Task requirements:
;Task requirements:
Calculate the next highest int from the digits of the following numbers:
Calculate the next highest int from the digits of the following numbers:
* 0
:* &nbsp; 0
* 9
:* &nbsp; 9
* 12
:* &nbsp; 12
* 21
:* &nbsp; 21
* 12453
:* &nbsp; 12453
* 738440
:* &nbsp; 738440
* 45072010
:* &nbsp; 45072010
* 95322020
:* &nbsp; 95322020



;Optional stretch goal:
;Optional stretch goal:
* 9589776899767587796600
:* &nbsp; 9589776899767587796600
<br><br>


=={{header|C}}==
=={{header|C}}==
Retrieved from "https://rosettacode.org/wiki/Next_highest_int_from_digits"