# Next Greater Number

Given an integer n, find the next number that follows the following requirements:

• The next greater number is a number where each digit, from left to right, is greater than or equal to the previous one. For example, 1455:

1<4

4<5

5<=5

• The next greater number has to be bigger than n

# Testcases

10 -> 11
19 -> 22
99 -> 111
321 -> 333
1455 -> 1456
11123159995399999 -> 11123333333333333


This is , so shortest code wins!

These numbers make up A009994 - Numbers with digits in nondecreasing order.

• I'd suggest not requiring answers to finish for the last test case. Doing so means that this is essentially a chameleon challenge - the focus is no longer on golfing, but on optimisation, an entirely different goal Jan 8, 2022 at 1:11
• Suggested test case: 1455 -> 1456 Jan 8, 2022 at 1:18
• Ohh Thats a very nice test case! i like how u exploit the number>n Jan 8, 2022 at 1:20
• Suggested test case: 321 > 333 Jan 8, 2022 at 1:21
• I'm guessing (and suggest that) you mean either "positive integer" or "non-negative integer", but if not what is the expected output for, say, -113? (Note that, strictly speaking, the digits of -113 are [-1, -1, -3] even though these might not be considered "digits"!), i.e. $-113=-1*100+-1*10+-1*1$, and as such the the answer would be -111 but most solutions would probably output -112) hence easiest to limit to at least "non-negative integers" Jan 8, 2022 at 2:41

# Brachylog, 3 bytes

<.o

?<.o.   # implicit input (?) and output (.)
?<.     # the input is smaller than the output
.o.   # the output is itself when ordered

• Reading this challenge I knew immediately Brachylog would be great for it. Jan 8, 2022 at 9:27

# Husk, 6 bytes

ḟoΛ≤d→


Try it online!

### Explanation

ḟoΛ≤d→
ḟ       find the first integer
→  starting from input incremented
o      such that composed function
Λ d   every digit
≤    is less that or equal to the previous


# Jelly, 7 bytes

‘DṢƑ$1#  Try it online! ## How it works ‘DṢƑ$1# - Main link. Takes n on the left
‘       - Yield n+1
$1# - Starting from n+1, find the first integer after such that: D - The digits are Ƒ - Invariant under Ṣ - Sorting  # Haskell, 52 41 bytes 9 bytes saved by AZTECCO and 2 bytes saved by xnor g(a:b)|[a]>b=a<$a:b|1>0=a:g b
g.show.(+1)


Try it online!

Solves all the cases nearly instantly.

# Explanation

The first thing to observe is that:

Find the smallest ascending digit number greater than $$\n\$$.

Is significantly harder than:

Find the smallest ascending digit number greater or equal to than $$\n\$$.

The former has a lot of edge cases around numbers that are themselves ascending in digits while the latter can be solved fairly easily.

But we can turn the latter to the former by just adding 1 before we run our algorithm. If g is the function that solves it then we just have g.show.(+1) to solve the actual problem.

So I solve the latter first:

g(a:b)|[a]>b=a<$a:b|1>0=a:g b  This goes along the list until either we meet a pair of digits that is descending (e.g. 21) or we reach the end. At that point we replace everything left with the digit we just read and exit. So for example 122334555612990 ^^ 122334555666666  Here's what the solution looks like without this observation just handling the edge cases naively: ### 92 bytes x!q@(a:b:c)|a>b=a<$q|1>0=(x++[a])!(b:c)
x!"9"=""!x++"1"
x!""="1"
f=(""!)


Try it online!

• @AZTECCO That's a very nice save. Jan 8, 2022 at 17:42
• Doesn't this produce larger numbers than needed sometimes because it targets the leftmost decrease, like for 98142?
– xnor
Jan 8, 2022 at 18:12
• @xnor I don't think so. What should 98142 produce? Jan 8, 2022 at 18:14
• Never mind, you're right, 99999 is the smallest
– xnor
Jan 8, 2022 at 18:16
• -2 bytes
– xnor
Jan 8, 2022 at 18:26

# Ruby, 35 bytes

->x{x.next![x.chars.sort*'']||redo}


Try it online!

-8 thanks to Dingus!

# R, 65 58 bytes

Or R>=4.1, 51 bytes by replacing the word function with a \.

Edit: -7 bytes thanks to @Dominic van Essen.

function(n){while(any(diff((n=n+1)%/%10^(n:0)%%10)<0))0
n}


Straightforward brute-force:

1. Increment n.
2. Split to digits (with leading 0s that don't matter).
3. Take differences.
4. If any of the differences is <0, loop back to 1. Otherwise, stop and output n.
• 58 bytes but for some reason doesn't work for moderately large test cases on TIO... (works fine on my laptop and at rdrr.io) Jan 8, 2022 at 20:10
• @Dominicvanessen TIO is on 3.5.2; apparently as of 3.6.2, the behavior for %/% changed for infinite values (from NEWS): "x %% L for finite x no longer returns NaN when L is infinite, nor suffers from cancellation for large finite L, thanks to Long Qu's PR#17611. Analogously, x %/% L and L %/% x suffer less from cancellation and return values corresponding to limits for large L." Jan 8, 2022 at 20:56

# Vyxal, 6 bytes

{›Ds≠|


Try it Online!

{      # While...
›     # Increment
D    # Make three copies
s≠  # Check if sorted
| # Do nothing


# Perl 5 -p, 26 bytes

1while++$_-join'',sort/./g  Try it online! The last test case would take about 194 hours (which is 8 days where I live). So I removed the last five digits from the test case to get the result in 7 sec. For "instant" result, also for the last big test case, this is a 78 byte suggestion: $_++;s/(@{[join"|",map$_."[0-".($_-1)."]",1..9]}).*/substr($1,0,1)x length$&/e ...try it online!

# C (gcc), 48 bytes

i;f(n){for(i=++n;n=n%10<n/10%10?++i:n/10;);i=i;}


Try it online!

# Julia 1.0, 34 31 bytes

~x=issorted("$(x+=1)") ? x : ~x  Try it online! # Python 2, 49 bytes f=lambda n:-~n*(list(-n)<sorted(~n))or f(-~n) Attempt This Online! Brute force: increments the given number until it is great. Unsurprisingly, chokes on the larger test case. #### Python, 77 bytes f=lambda n,t=1:(n:=n+t)*([*str(n)]<=sorted(str(n)))or 10*(g:=f(n//10,0))+g%10 Attempt This Online! This constructs the result directly. Handles all test cases. # Python 3, 84 f=lambda n:n+1if all(int(i)<=int(j)for i,j in zip(str(n+1),str(n+1)[1:]))else f(n+1)  Fails on the last case due to exceeding the maximum recursion depth. • Welcome to the site! The spaces between ) and other tokens like for and else are not needed, you can remove them to save bytes. Jan 8, 2022 at 10:41 • @WheatWizard Thanks! If you got any other tips, I'll be glad to utilize them. Jan 8, 2022 at 10:47 • Sure we have an entire question to catalog python tips that you can check out. Jan 8, 2022 at 10:54 # C (gcc), 59 48 bytes f(n,t){t=++n?t=f(n/10-1),10*t+t%10:0;n=t>n?t:n;}  Try it online! f(n,t){ t=++n // increment input ? t=f(n/10-1), // recurse on prefix 10*t+t%10 // and append its last digit : 0; // (base case =0) n=t>n?t:n; // max of above and input }  # PowerShell, 48 bytes Very simply iterates through numbers starting from the input until a number equals the sorted string representation of itself, then returns that number. param($n)for(;++$n-ne-join("$n"|% T*y|sort)){}$n  Try it online! # Retina 0.8.2, 67 bytes T9dd.9*$
^0
10
.
$*_¶ +((_+¶)(?!_*\2)(_*¶)*)_*¶$
$2$1
(_+)¶
$.1  Try it online! Link includes test cases. Explanation: T9dd.9*$


Increment the input.

^0
10


Deal with any carry.

.
$*_¶  Convert each digit to unary. +((_+¶)(?!_*\2)(_*¶)*)_*¶$
$2$1


Propagate the first digit greater than its successor to the end of the number. E.g. 11123159995400000, 11123315999540000, 11123331599954000, ... 1123333333333331, 1123333333333333.

(_+)¶
$.1  Convert the digits back to decimal. • "Increment the input" can be shorter: .+(linefeed)$.(*..
– m90
Jan 9, 2022 at 4:46
• @m90 Not in Retina 0.8.2
– Neil
Jan 9, 2022 at 8:15

# Charcoal, 25 bytes

≔Ｉ⊕Ｎθ…θ⌕Ｅθ›ι§θ⊕κ¹×⁻Ｌθⅈ§θⅈ


Try it online! Link is to verbose version of code. Explanation:

≔Ｉ⊕Ｎθ


Input n, increment it, and turn it into a string.

…θ⌕Ｅθ›ι§θ⊕κ¹


Print the prefix up to the first digit that is greater than its subsequent digit. (There is an edge case here when all the digits are equal but the remaining code will just fill with that digit because it has no other choice.)

×⁻Ｌθⅈ§θⅈ


Fill the rest of the string with that digit.

# Japt, 8 bytes

È-ìn}fUÄ


Try it

# MathGolf, 7 bytes

)∙▒sy=▼


Try it online.

Explanation:

      ▼ # Do-while false with pop:
)       #  Increase the current integer by 1
#  (which will be the implicit input in the first iteration)
∙      #  Triplicate it
▒     #  Convert the top copy to a list of digits
s    #  Sort those digits
y   #  Join it back together to an integer
=  #  Check if the sorted integer is still the same as the triplicated integer
# (after the do-while loop, output the entire stack implicitly as result)


# Pip, 8 bytes

T$<=Ua_a  Attempt This Online! ### Explanation  ; a is command-line argument T ; Loop till Ua ; Increment a, and$        ;   Fold on
<=      ;   Less-than-or-equal
; is true:
_   ;   No-op
a  ; After the loop, autoprint the modified value of a


Folding a number such as 1455 on <= is the equivalent of computing 1 <= 4 <= 5 <= 5, which (thanks to Pip's chaining comparison operators) is equivalent to (1 <= 4) & (4 <= 5) & (5 <= 5).

Here's a 19-byte version that can handle the largest test case:

O@Ua{y?ya>b?Yab}MPa


Attempt This Online!

O@Ua{y?ya>b?Yab}MPa
Ua                 ; Increment a
@                   ; Get its first digit
O                    ; Output it without a newline
{          }MPa  ; Map this function to each pair of adjacent digits in a:
y?              ;   Has y been assigned yet?
y             ;   If so, use that as the next digit
a>b?         ;   Otherwise, is the first digit of the pair greater than
;   the second digit of the pair?
Ya       ;   If so, assign the first digit to y and use that
b      ;   Otherwise, use the second digit


# 05AB1E, 6 bytes

[>Ð{Q#


Try it online or verify almost all test cases (except for the last one, which is shortened a bit).

Explanation:

[       # Loop indefinitely:
>      #  Increase the current value by 1
#  (which will be the implicit input in the first iteration)
Ð     #  Triplicate it
{    #  Sort the digits in the top copy
Q   #  Pop it and another copy and check if they're still the same
#  #  If it is: stop the infinite loop
# (after which the remaining third value is output implicitly as result)


Here a different approach which also handles the largest test case (14 bytes):

>Dü›Å¡ćJs˜¬s∍«


Explanation:

               #  E.g. input = 11123159995399999
>              # Increase the (implicit) input-integer by 1
#  STACK: 11123159995400000
D             # Duplicate it
#  STACK: 11123159995400000,11123159995400000
ü            # For each overlapping pair of digits:
›           #  Check if the first is larger than the second
#   STACK: 11123159995400000,[0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0]
Å¡         # Split the (implicit) input-integer at the truthy positions
#   STACK: [[1,1,1,2],[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]]
ć        # Extract head; pop and push first list and remainder-lists
# separated to the stack
#  STACK: [[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]],[1,1,1,2]
J       # Join this first list together to a single integer
#  STACK: [[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]],1112
s      # Swap to get the remainder-list
#  STACK: 1112,[[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]]
˜     # Flatten it
#  STACK: 1112,[3,1,5,9,9,9,5,4,0,0,0,0,0]
¬    # Push its first digit (without popping the list)
#  STACK: 1112,[3,1,5,9,9,9,5,4,0,0,0,0,0],3
s   # Swap so the list is at the top
#  STACK: 1112,3,[3,1,5,9,9,9,5,4,0,0,0,0,0]
∍  # Extend this digit to the length of this list
#  STACK: 1112,3333333333333
« # Append the two strings together
#  STACK: 11123333333333333
# (after which the result is output implicitly)


APL 1612 16 bytes

New Approch

10⊥⌈/\⍎¨⍕1∘+

It's just a append scan and then maximum of each cell doesnt work in case idetified by @ova

1∘+⍣{∧/2≤/⍎¨⍕⍺}

Explanation

1∘+ adds 1

{∧/2≤/⍎¨⍕⍺} checks weather each number is bigger than the one preceding it

1∘+⍣{∧/2≤/⍎¨⍕⍺} continously adds 1 untill the previous function returns true i.e. A fixed point function

• This returns 15599 for 15195, where 15555 would be enough. 1∘+⍣{∧/2≤/⍎¨⍕⍺} did handle this correctly
– ovs
Jan 10, 2022 at 11:29
• Thanks for catching it, the second one will works as intended I will be removing the first one @ovs Jan 10, 2022 at 14:17

# Desmos, 159155 149 bytes

The code below supports all integers, with negative integers supported as described in Jonathan Allan's comment.

o->T(o+1-sign(o-c)min(1-sign(L-sort(L))^2)),c->T(c)
i=0
o=0
c=0
s=sign(o)
a=abs(o)
L=smod(floor(a/10^{[floor(log(a+1-ss))...0]}),10)
T(n)=\{i=c:n,i\}


Try It On Desmos!

Try It On Desmos! - Prettified

This uses a variable c to cache the input so that changes in the input can be detected (with the function T(n)), causing the rest of the program to react accordingly (That is why the program won't break if the input is changed while the ticker is still running).

The byte count can actually be lowered significantly if some liberties (A.K.A. removing the caching variable) can be taken with the I/O method:

### 127123 117 bytes, with modified I/O method

o->o+1-sign(o-i)min(1-sign(L-sort(L))^2)
i=0
o=0
s=sign(o)
a=abs(o)
L=smod(floor(a/10^{[floor(log(a+1-ss))...0]}),10)


Try It On Desmos!

Try It On Desmos! - Prettified

This version removes the caching variable c and the function T(n) completely, which means that the code cannot detect any changes in the input. This means that extra steps have to be taken in order to enter in or change the input and run the code.

I'm not too sure which I/O method is considered the "accepted" version, so I'm putting both.

Also, it's unclear whether or not we have to support negative integers. If we only have to support non-negative integers or positive integers, the code can be shortened even more (the code below uses the caching variable):

### 140 134 bytes, supports all non-negative integers

o->T(o+1-sign(o-c)min(1-sign(L-sort(L))^2)),c->T(c)
i=0
o=0
c=0
L=mod(floor(o/10^{[floor(log(a+1-sign(o)))...0]}),10)
T(n)=\{i=c:n,i\}


Try It On Desmos!

Try It On Desmos! - Prettified

### 128 122 bytes, supports positive integers

o->T(o+1-sign(o-c)min(1-sign(L-sort(L))^2))),c->T(c)
i=1
o=1
c=0
L=mod(floor(o/10^{[floor(logo)...0]}),10)
T(n)=\{i=c:n,i\}


Try It On Desmos!

Try It On Desmos! - Prettified

# tinylisp, 95 bytes

(load library
(d F(q((N)(i(e N(from-base 10(merge-sort(to-base 10 N))))N(G N
(d G(q((N)(F(a N 1


Try it online!

-3 from dlosc

merge-sort is shorter than insertion-sort. Surprisingly there's no plain sort alias. Since variable assignment is global, i've resorted to using (+ n 1) everywhere.

• if -> i, drop the close paren on the first line, and then you can save one more byte by doing the increment in a helper function: Try it online! Feb 1, 2022 at 17:56

# Factor + math.unicode, 49 bytes

[ [ 1 + dup present [ <= ] monotonic? ¬ ] loop ]


Try it online!

Add 1. If the string representation of the number isn't sorted, repeat.

# Pari/GP, 39 bytes

a->until(vecsort(d=digits(a))==d,a++);a


Try it online!

# APL+WIN, 48 bytes

Prompts for integer

n←⍴v←⍎¨⍕⎕+1⋄10⊥⌽((n-⍴v)⍴¯1↑v),⌽v←(^\0≤1,-2-/v)/v


Try it online! Thanks to Dyalog Classic

The final example throws an error in the final digit in Dyalog Classic on TIO. Dropping the last digit of that example gives the expected result.

# JavaScript (Node.js), 39 bytes

f=n=>(p=[...++n+''])+''>p.sort()?f(n):n


Try it online!

# Ly, 14 bytes

1[psSaJlf=!]p


Try it online!

This is a pretty straightforward iterative take on the question. It splits the number into digits, sorts them, collapses back to a number, and compare that to the original. The loop ends when the digits are sorted.

1              - push a '1' to start the loop
[p         ]  - loop until the top of the stack is '0'
- increment the current var (first time reads STDIN)
s          - save number to backup cell
S         - split the number into digits
a        - sort the stack
J       - recombine the digits into a number
l      - pull the number from the backup cell
f     - flip the top two entries of the stack
=    - compare the original and sorted digits
!   - negate result of comparison
p - delete iterator var, leaves the answer on the stack


$_++;s/./$t||($&<$%10?$t=$%10:$&)/ge  Try it online! It's a little longer than @KjetilS' answer, but it has the advantage of being nearly "instant" for any number. Its runtime is based on the length of the number rather than the value. For really big numbers, -Mbigint should be added to the command line flags. # Raku, 27 bytes {first {[<=] .comb},$_^..*}


Try it online!

• $_ ^.. * is the infinite sequence of numbers starting with, but not including (thanks to the ^), the input number $_.
• first { ... }, ... returns the first number in that sequence for which the brace-delimited anonymous function returns a true value.
• .comb splits the input number into its individual digits.
• [<=] reduces the digits with the <= operator. It's equivalent to digit₁ <= digit₂ <= ... <= digitₙ.