Next Greater Number

Question

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 code-golf, so shortest code wins!

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

Answer 1

Brachylog, 3 bytes

<.o

Try it online! or Try more cases

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

Answer 2

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

Answer 3

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

Answer 4

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"
x!y=x++show(1+read y)
f=(""!)

Try it online!

Answer 5

Ruby, 35 bytes

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

Try it online!

-8 thanks to Dingus!

Answer 6

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}

Try it online! Try it on rdrr.io (for larger test-cases)!

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.

Answer 7

Vyxal, 6 bytes

{›Ds≠|

Try it Online!

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

Answer 8

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!

Answer 9

C (gcc), 48 bytes

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

Try it online!

Answer 10

Julia 1.0, ³⁴ 31 bytes

~x=issorted("$(x+=1)") ? x : ~x

Try it online!

Answer 11

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.

Answer 12

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.

Answer 13

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
}

Answer 14

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!

Answer 15

Retina 0.8.2, 67 bytes

T`9d`d`.9*$
^0
10
.
$*_¶
+`((_+¶)(?!_*\2)(_*¶)*)_*¶$
$2$1
(_+)¶
$.1

Try it online! Link includes test cases. Explanation:

T`9d`d`.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.

Answer 16

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.

Answer 17

Japt, 8 bytes

È-ìn}fUÄ

Try it

Answer 18

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)

Answer 19

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

Answer 20

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∍«

Try it online or verify all test cases.

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)

Answer 21

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

Answer 22

Desmos, 159 155 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:

127 123 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

Answer 23

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.

Answer 24

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.

Answer 25

Pari/GP, 39 bytes

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

Try it online!

Answer 26

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.

Answer 27

JavaScript (Node.js), 39 bytes

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

Try it online!

Fixed tsh's answer

Answer 28

Ly, 14 bytes

1[p`sSaJlf=!]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

Answer 29

Perl 5 -p, 38 bytes

$_++;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.

Answer 30

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ₙ.