# Fill in the next numbers

Given a list of integers, output a list where the $$\ i \$$th element of the list equals the first number in the input list which is $$\ \ge i \$$, until there are no such numbers.

For example, if the input is:

2 3 5 7 11


then we "expand" the sequence out to show where the gaps are:

_ 2 3 _ 5 _ 7 _ _ __ 11     # input
1     4   6   8 9 10        # gaps


Now we fill in the blanks with the next number that is in the sequence in each case:

2 2 3 5 5 7 7 11 11 11 11
1     4   6    8  9 10


This is the output.

## Test cases

[1]               -> [1]
[3]               -> [3, 3, 3]
[1, 2, 3]         -> [1, 2, 3]
[1, 3, 4, 9]      -> [1, 3, 3, 4, 9, 9, 9, 9, 9]
[2, 3, 5, 7, 11]  -> [2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11]


## Rules

• Sandbox Commented Mar 7, 2022 at 6:42

# R, 30 bytes

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

function(x)rep(x,diff(c(0,x)))


Try it online!

# Python 3, 37 bytes (@Jitse)

f=lambda l=[],*L:l and[l]*l+f(*L)[l:]


Try it online!

### Original Python 3, 38 bytes

f=lambda l,*L:(l,)*l+(L and f(*L)[l:])


Try it online!

Takes the splatted input and returns a tuple.

### How?

This is entirely based on the observation that the first original number k, say, will occur k times in the output. Working back to front we can treat each number k[n] as if it were the first and at the next iteration n-1 replace the k[n-1] excess copies of k[n] with copies of k[n-1].

• this is pure genius! Commented Mar 8, 2022 at 3:35
• 37 bytes Commented Jan 17, 2023 at 12:52
• @Jitse Nice. Somehow, I would have expected this to be a syntax error but it isn't. Commented Jan 21, 2023 at 17:22

# BQN, 5 bytes

+⁼/⊢


Try it at BQN online REPL

BQN has a lovely 'undo' modifier (⁼) which calculates the inverse of any function, where this is possible.
Here we use it with cumulative sum (+ ) to get the cumulative differences starting from zero.
After that we just need to replicate (/) the input values (⊢) this number of times.

   /    # Replicate the elements of
⊢   # the right-hand argument
# by
⁼     # undo the
+      # cumulative sum of
# the right-hand argument


# Ruby, 36 bytes

->l{x=0;l.flat_map{|a|[a]*(-x+x=a)}}


Try it online!

# Vyxal, 4 bytes

ẋ∩vg


Try it Online!

ẋ    # Repeat the numbers by themselves
# [[2, 2], [3, 3, 3], [5, 5, 5, 5, 5]]
∩   # Transpose
# [[2, 3, 5], [2, 3, 5], [3, 5], [5], [5]]
vg # Get the minimum of each


# PARI/GP, 35 bytes

a->vector(a[#a],n,[m|m<-a,m>=n][1])

Attempt This Online!

a->                                   Define a function with argument a
vector(                        )   that returns a vector
a[#a],                      whose length is the last term of a
n,                    and the nth term
[m|m<-a,    ][1]    is the first m in a such that
m>=n        m is larger than n.

• Could you add an explanation? Since this is language of the month, that would give those of us who don't know the language a bit of an on-ramp. Commented Mar 7, 2022 at 14:12

# JavaScript (Node.js), 40 bytes

a=>a.map(g=n=>n>o.push(n)&&g(n),o=[])&&o


Try it online!

# Python 3.8 (pre-release), 43 bytes

f=lambda n,i=2:n and[n[0]]+f(n[[i]>n:],i+1)


Try it online!

Thanks @dingledooper for -2 bytes.

• 44 bytes: f=lambda n,i=2:n and[n[0]]+f(n[i>n[0]:],i+1). Commented Mar 7, 2022 at 7:56
• Actually, there's 43 bytes: f=lambda n,i=2:n and[n[0]]+f(n[[i]>n:],i+1). Commented Mar 7, 2022 at 8:00

# K (ngn/k), 6 bytes

(-':)#


Try it online!

## Explanation

(-':)#
(-':)  deltas
# replicate

• Nice! I just threw together {,/(-':x)#'x} for K4 but this is much more impressive!
– mkst
Commented Mar 9, 2022 at 9:30
• It's quite useful to be following the development of ngn/k :P Commented Mar 9, 2022 at 13:38
• i think this should work in the current k9 build as well) Commented Mar 9, 2022 at 13:41

# Factor, 44 bytes

[ dup last iota [ '[ _ > ] find ] with map ]


Try it online!

Let $$\L\$$ be the last element of the input. Then map $$\[0..L)\$$ to the first element of the input that is greater.

# APL+WIN, 13 bytes

Prompts for input

(-2-/0,v)/v←⎕


Try it online! Thanks to Dyalog APL Classic

# Halfwit, 7.5 bytes

MZ;RZMR[$ Try It Online! I think I made it too minimalistic... ## Explanation M ; # Map over each value... Z # Fill an array of length (itself) with (itself) R # Reduce by (taking two lists) Z # Zip M # For each pair... R # Reduce by... [ # If the first is truthy (nonzero)...$ # return it, otherwise return the other value

• Half-bit? Do you mean half-byte? Commented Mar 7, 2022 at 9:38
• Given the image, I feel obligated to mention that the name "Samwise" is roughly based on the Old English for "halfwit." Commented Mar 7, 2022 at 17:49
• @pxeger Oops lol :) - I think I'll just leave it like that Commented Mar 7, 2022 at 18:51
• I've posted my first Halfwit answer. A few questions/suggestions: 1) is there an easier way to push 4? 2) I would try to remove the BigInt/int error when you use operations on mixed types. 3) Can anything be done with strings? The challenge originally asked for a space-delimited string of integers, but I don't think Halfwit has anything useful to split those spaces? Although it does allow for string inputs, I assume the language is primarily designed for int/int-lists (and it converts strings to codepoint integers), right? Commented Apr 21, 2022 at 13:42
• @KevinCruijssen strings are represented as charcodes, and there’s not much you can do with them. Halfwit’s very experimental lol Commented Apr 30, 2022 at 9:18

# Julia 1.0, 29 bytes

!x=[fill.(x,diff([0;x]))...;]


Try it online!

# MATL, 6 bytes

0yhdY"


Try it online!

Take a diff and repelem the input that many times (same as @pajonk's R answer among others).

I thought this sounded ideal for an interp1 based answer, but that comes out to 16 bytes: 0ihttX>:IG1)5$Yn Try it online! # Octave, 26 bytes @(v)repelem(v,diff([0,v]))  Ideone link (TIO's version of Octave doesn't seem to have repelem.) This started off as seeing if I'd have better luck with interp1 on Octave directly (than via MATL), but it's again longer here, at 45 bytes: @(v,w=[0,v])interp1(w,w,1:max(v),'next',v(1))  Try it online! (the w=[0,v] is because interp1 doesn't like operating on single element vectors like the [3] testcase, wants at least two elements.) # Pip, 13 11 bytes -2 bytes by porting Neil's Charcoal answer because I was seriously overthinking things FngT Ui=Pn0  Takes input as separate command-line arguments; gives output as lines of stdout. Attempt This Online! ### Explanation FngT Ui=Pn0 ; i is 0, g is list of command-line args (implicit) Fng ; For each n in g: T ; Till Ui ; increment i = ; equals Pn ; print n: 0 ; No-op  # Desmos, 45 bytes M=l.max f(l)=[\{l<i:M,l\}.\min\for i=[1...M]]  Try It On Desmos! Try It On Desmos! - Prettified I feel like this could be a bit shorter, though I don't see it at the moment. I tried to take out the two uses of l.max but the strategies I tried didn't work. Also that piecewise expression is a bit annoying, though I don't see a shorter way (it causes me to add \'s everywhere in the list comprehension. Without the \'s the code won't work.). # HBL, 9 bytes -(2*(<1.?)(2-.(10.  The online interpreter doesn't support zip-with yet, but here's a version with a hacked-together reimplementation of zip-with on the first line: Try it! ### Explanation -(2*(<1.?)(2-.(10. (2 ) Zip - with the subtraction function: . The input list, and (1 ) Cons 0 0 to . the input list Result: pairwise differences (< ) For each item in . the input list: 1 cons it to ? nil Result: input list but with each number in a singleton list (2 ) Zip those two lists * with the list-repetition function Result: for each n in the input list, a length-n list of n's - Flatten  # Haskell, 37 34 bytes f l=do(a,b)<-zip(0:l)l;b<$[a+1..b]


Try it online!

• Saved 3 Bytes thanks to @Unrelated String suggesting using do notation which reveals how emphatic Haskell is.

Old version

f l=(\(a,b)->b<$[a+1..b])=<<zip(0:l)l  # Jelly, 4 bytes xŻI$


A monadic Link that accepts a strictly increasing list of positive integers and yields a non-strictly increasing list of positive integers.

Try it online!

### How?

If the input is A=[a1, a2, a3, ...] then the output needs to be a1 a1s followed by a2-a1 a2s then a3-a2 a2s etc.

xŻI$- Link: strictly increasing list of positive integers, A$ - last two links as a monad - f(A=[a1, a2, a3, ...]):
Ż   -   prepend a zero -> [0, a1, a2, a3, ...]
I  -   incremental differences -> [a1, a2-a1, a3-a2, ...]
x    - times (vectorises) -> [a1, ..., a1, a2, ..., a2, a3, ...]


sub{$l=0;map{($_)x($l+=$r=$_-$l,$r)}@_}  Try it online! # R, 41 bytes function(x)x[cumsum(y<-1:rev(x)%in%x)+!y]  Try it online! Quite a lot longer than pajonk's answer, but a nice little bit of index calculation all the same. This ports to other matrix languages such as, for instance, MATL, but it's longer than the diff approach there as well. # Arturo, 42 bytes $[a][map 1..max a'x[min select a'y[y>=x]]]


Try it

$[a][ ; a function taking an argument a map 1..max a'x[ ; map over the range 1..max(a) and assign current value to x min select a'y[ ; select the smallest number in a that... y>=x ; is greater than or equal to x ] ; end select ] ; end map ] ; end function  # JavaScript (Node.js), 38 bytes a=>a.map(g=n=>n>++i?[n,g(n)]:n,i=0)+''  Try it online! # Jelly, 4 bytes x)o/  Try it online! Shamelessly sandbox sniped, but I didn't start it :P  ) For each element of the input, as a monadic chain: x repeat it by itself. o/ Reduce the resulting list of lists by logical OR.  # 05AB1E, 87 6 bytes Å1*ζ€ß  -1 byte porting @emanresuA's Vyxal answer Original 8 7 bytes answer: 0š¥Å1*˜  Explanation:  # e.g. input=[2,3,5] Å1 # Map each value in the (implicit) input-list to that many 1s # → [[1,1],[1,1,1],[1,1,1,1,1]] * # Multiply each to the (implicit) input-list at the same positions # → [[2,2],[3,3,3],[5,5,5,5,5]] ζ # Zip/transpose; swapping rows/columns, using " " as filler # → [[2,3,5],[2,3,5],[" ",3,5],[" "," ",5],[" "," ",5]] €ß # Get the minimum of each inner list, ignoring the " " # → [2,2,3,5,5] # (after which the resulting list is output implicitly) 0š # Prepend a 0 to the (implicit) input-list # → [0,2,3,5] ¥ # Pop and push its deltas/forward-differences # → [2,1,2] Å1* # Similar as above # → [[2,2],[3],[5,5]] ˜ # Flatten this list of lists # → [2,2,3,5,5] # (after which the resulting list is output implicitly)  # Python 3.8 (pre-release), 75 bytes def f(a): s=[i:=(c:=a[-1])] while i:=i-1:s=[c:=[c,i][i in a]]+s print(s)  Try it online! Ungolfed: def fill_numbers(original): current_number = last_valid = original[-1] result = [original[-1]] while current_number-1 > 0: current_number -= 1 if current_number in original: last_valid = current_number result = [last_valid] + result print(result)  # Pyth, 9 bytes hM.Tm*d]d  Try it online! # Charcoal, 9 bytes ＦＡＷ‹ⅉι⟦Ｉι  Try it online! Link is to verbose version of code. Explanation: ＦＡ  Loop over the input list. Ｗ‹ⅉι  Repeat until the appropriate line is reached... ⟦Ｉι  ... output the current value on its own line. # PHP, 71 bytes $n=[];for($i=max($a);$i;$i--){$n=[in_array($i,$a)?$h=$i:$h??$i,...$n];}


Try it online!

Ungolfed:

$n = []; for ($i = max($a);$i; $i--) {$n = [in_array($i,$a) ? $h =$i : $h ??$i, ...\$n];
}
`