# 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 are A009994

• 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 at 1:11
• Suggested test case: 1455 -> 1456 Jan 8 at 1:18
• Ohh Thats a very nice test case! i like how u exploit the number>n Jan 8 at 1:20
• 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 at 2:41
• These numbers are A009994. Jan 8 at 6:50

# 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 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  • caird would you mind explaining the code? not meaning to waste your time but it really helps explain how your code actually works Jan 8 at 1:12 # 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 at 17:42
• Doesn't this produce larger numbers than needed sometimes because it targets the leftmost decrease, like for 98142?
– xnor
Jan 8 at 18:12
• @xnor I don't think so. What should 98142 produce? Jan 8 at 18:14
• Never mind, you're right, 99999 is the smallest
– xnor
Jan 8 at 18:16
• -2 bytes
– xnor
Jan 8 at 18:26

# 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 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 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!

# Ruby, 35 bytes

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


Try it online!

-8 thanks to Dingus!

# C (gcc), 48 bytes

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


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.

• really nice u passed the last test case! Jan 10 at 9:35

# 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 at 10:41
• @WheatWizard Thanks! If you got any other tips, I'll be glad to utilize them. Jan 8 at 10:47
• Sure we have an entire question to catalog python tips that you can check out. Jan 8 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 at 4:46 • @m90 Not in Retina 0.8.2 – Neil Jan 9 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=▼  Port of my 05AB1E answer. 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 at 11:29 • Thanks for catching it, the second one will works as intended I will be removing the first one @ovs Jan 10 at 14:17 # Julia 1.0, 34 bytes ~x=while !issorted("$(x[]+=1)")end


Try it online!

by bruteforcing, input is a singleton and the function mutates it

# Julia 1.0, 38 bytes

!a=(m='0';map(i->m=max(i,m),"\$(a+1)"))


Try it online!

more efficient approach, allowing to compute the bigger test case. Input is a number and output is a string

# 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 at 17:56

# 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!

# Factor + math.unicode, 49 bytes
[ [ 1 + dup present [ <= ] monotonic? ¬ ] loop ]