Find the first run of numbers summing to n

Question

Given as input a positive nonzero integer n >= 10 and a sequence of digits 0-9 (which may be taken as a string or a list), find the first contiguous subsequence of digits in the sequence that sums to n and output the start and end indexes. You may use zero- or one-based indexing. If no such subsequence exists, your program may output any constant value.

Examples

These examples use zero-based indexing.

Input: 10 123456789
Output: 0 3
Input: 32 444444444
Output: 0 7
Input: 15 123456789
Output: 0 4
Input: 33 444444444
Output: No solutions

This is code-golf, so shortest program wins!

• mousetail: Is it ok to output as start, length instead of start, end?
• Ginger: @mousetail Nope.
• Ginger: @NahuelFouilleul Yes, as long as you make that clear in your answer.
• Kjetil S: A test case resulting in a non-zero offset would help in ensuring correctness.
• Neil: Indices is the correct plural in a mathematical context. (But databases have indexes.)

Answer 1

Excel (ms365), 155 bytes

Assuming list as input and 0-indexed output:

enter image description here

Formula in C1:

=LET(x,TOCOL(B:B,1),y,COUNT(x),REDUCE("No solutions",SEQUENCE(y),LAMBDA(a,b,IFERROR(HSTACK(y-b,y-b+MATCH(A1,SCAN(0,DROP(x,y-b),LAMBDA(c,d,c+d)),0)-1),a))))

The idea here is to use SCAN() to iterate from each element in reversed order in column B and MATCH() the value in A1 against each resulting array. If found, then HSTACK() both the current iteration and the position the element is found.

Unfortunately this process is rather verbose in Excel, but fun to attempt this challenge nonetheless.

---

enter image description here enter image description here enter image description here

• Kevin Cruijssen: No solutions can be x, since it's allowed to output any constant value. 🤷

Answer 2

R 4.1, (削除) 78 bytes (削除ここまで) (削除) 71 bytes (削除ここまで) 65 bytes

v1.2 65 bytes

-5 bytes thanks to pajonk:

1. -4 for pointing out that F <- F + 1;k <- m[, F];sum(s[k:k[2]]) can be expressed as sum(s[(k <- m[, F <- F + 1]):k[2]]). This also means you can lose the curly braces as the expression is on one line, and you do not need semi-colons.
2. -1 because while(a!=b) can actually be expressed as while(a-b). This is safe as negative numbers are also TRUE when coerced to logical.

(And also -1 byte by pointing out I had miscounted.)

\(s,n,m=combn(seq(s),2)){while(sum(s[(k=m[,F<-F+1]):k[2]])-n)0
k}

Attempt This Online!

v 1.1 71 bytes

\(s,n,m=combn(seq(s),2)){while({F=F+1;k<-m[,F];sum(s[k:k[2]])!=n})0
k}

-7 bytes thanks to Giuseppe

Two changes:

1. Not replacing seq() with the unary - as it's only being used once (I was using it twice before and failed to notice that was no longer the case).

2. Replacing j with F is yet another ludicrous thing that R allows you to do that I would never have tried in the vein of these coercion tips by @rturnbull (link from Giuseppe - thanks). For non-R uses, T and F are built-in aliases for TRUE and FALSE. This means you can do this:

T == TRUE # TRUE
F == FALSE # TRUE
F == TRUE # FALSE
F <- F+1
F == FALSE # FALSE
F == TRUE # TRUE

I have no idea why this is allowed in R but it's saved 5 characters compared with initialising j.

v.1.0 78 bytes

\(s,n,`-`=seq,j=0,m=combn(-s,2)){while({j=j+1;k<-m[,j];sum(s[k:k[2]])!=n})0
k}

Attempt this online

How?

This is a function which expects a vector, s and a target value n, as arguments. Basically it does this:

1. Uses combn() to create a m, a matrix of all possible length 2 combinations of the indices of s. E.g. combn(1:5,2) produces:

 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 1 1 1 1 2 2 2 3 3 4
[2,] 2 3 4 5 3 4 5 4 5 5

2. Loops through the columns of this to subset s, using row 1 as the start index and row 2 as the end index.

3. Breaks the loop if the subset adds up to n. It exits with an error if there is no solution. I wasn't entirely clear if an error counts as a constant, but this nice Python answer behaves in the same way, which I took as a green light.

4. There are a couple of golfing tricks both from Giuseppe. Taking advantage of how seq(s) behaves if s is a vector and reassigning the unary - with `-` = seq, means we can do m = combn(-s, 2) instead of the positively verbose m = combn(seq_along(s), 2).

The test cases are included in the footer of ATO link. Only my second Code Golf answer ever so very interested in any suggestions / improvements.

• Giuseppe: As nice as the seq trick is, it's shorter to just use it directly since you're only using it once, so combn(seq(s),2), and using F instead of j should save another few: ATO
• SamR: @Giuseppe you're right! I was using it twice in a previous version. I had no idea you could increment T and F like that. So on the first iteration of the loop, F==FALSE is FALSE and F==TRUE is TRUE. That is truly bonkers. Thanks for the suggestions.
• Giuseppe: Yes, F is initialized to FALSE which gets coerced to a numeric (specifically, 0) when you do the addition; similarly, T is initialized to TRUE which converts to 1 when you do arithmetic. This tip has some additional examples of implicit type conversions, but there are others; notably F and T will coerce to "FALSE" and "TRUE", respectively, when converted to a character
• pajonk: 1. I think your solution is actually 70 bytes. 2. 66 bytes by inlining what's possible and getting rid of semicolons and braces.
• pajonk: Another -1 byte by replacing != with - -- sorry I missed it the in the previous golf.

Answer 3

><> (Fish), 126 bytes

i01:}r[l0$>:?v~]}r4[{:}]=?v1+$:@$:@l5-$-)?v20.
/[-2lr@@+@:$@/ ;n+oan:$/-3lr1;?=-2l:+1~/ 
\}]r1-a0. \[}]r20.

Try it

Explanation

enter image description here

Takes the array of characters as the initial value of the stack and the target as the input over STDIN. Outputs nothing if no solution exists, and an exclusive range if it does.

i01 push the target value, the start of the range, and the length to the stack.

:}r[l0$>: Push the top "length" elements of the stack to a new stack. Set it's length, that's the amount of elements we want to compare.

@$:@+@@rl2-]}]r1-a0. This adds the top of the stack to the accumulator, rotates the stack, then subtract one from the number of remaining rotations necessary.

~]} pop 0, the remaining number of rotations, and combine the stack back with the previous. Now the sum of the top N elements of the input are on top of the stack.

r4[{:}]= Copy the target sum to the end of the input.

=?v
 \$:nao+n;

If the sum equals the target, output.

1+$:@$:@15-$-)?v Add one to the length. If it's greater than the remaining length of the list go down.

~1+:l2-=?; Add one to the starting value. If it's greater than the length of the input exit.

1rl3-[}]r Set the length back to 1. Shift the rest of the stack over one so it starts at the second position.

Answer 4

05AB1E, 11 bytes

ā<ã.Δ1sŸèOQ

Inputs in the order sequence, n.
0-based output; will output -1 if no result can be found; and [i,i] if n is a single digit that's present in the input-sequence.

Try it online or verify all test cases.

Explanation:

ā # Push a list in the range [1, length of the first (implicit) input sequence]
 < # Decrease each by to make it a 0-based [1,length)
 ã # Cartesian power of 2 to get all possible pairs of this list
 .Δ # Find the first pair that's truthy for:
 1 # Push the first input-sequence again
 s # Swap so the current pair is at the top
 Ÿ # Pop and push a list in the range of this pair
 Ù # Uniquify this list (in case the pair was [a,a])
 è # Index each into the first input-sequence
 O # Sum these digits together
 Q # Check if this sum is equal to the second (implicit) input
 # (after which the result is output implicitly)

Answer 5

Vyxal g, 11 bytes

ẏ:Ẋ'ƒṡ1İ∑0=

Try it Online!

A simple little approach.

Explained

ẏ:Ẋ'ƒṡ1İ∑0=
ẏ: # The range [0, len(input)), twice.
 Ẋ # cartesian product of the two lists and sort to get the first
 ' # get all items of that where
 ƒṡ # the list turned into an inclusive range between the two numbers
 1İ # indexed into the sequence of numbers
 ∑0= # summed equals n
# g flag gets the smallest pair

• The Thonnu: Is the first s required? It seems to work fine without it.

Answer 6

Python 3.8 (pre-release), 75 bytes

f=lambda v,l,a=0,b=1:v==(q:=sum(l[a:b]))and(a,b-1)or f(v,l,a+(q>v),b+(q<v))

Try it online!

Switched to a list of integers instead of a string for -9 bytes

old:

f=lambda v,l,a=0,b=1:v==(q:=sum(map(int,l[a:b])))and(a,b-1)or f(v,l,a+(q>v),b+(q<v))

Try it online!

Takes an integer and a string as input. Returns a tuple with start and end index if a solution is found, and an error if not.

Answer 7

JavaScript (ES6), 64 bytes

-1 thanks to @l4m2

Expects (n)(array). Returns either [start, end] or false.

n=>a=>a.some((_,i)=>a.some((v,j)=>j<i||(s-=v)?0:o=[i,j],s=n))&&o

Try it online!

Commented

n => // n = target sum
a => // a[] = array of digits
a.some((_, i) => // for each digit at index i in a[]:
 a.some((v, j) => // for each digit v at index j in a[]:
 j < i || // if j is less than i
 (s -= v) // or subtracting v from s
 ? // does not result in 0:
 0 // do nothing
 : // else:
 o = [i, j], // set o = [i, j] and exit
 s = n // start with s = n
 ) // end of inner some()
) // end of outer some()
&& o // if successful, return o[]

• l4m2: tio.run/…

Answer 8

Japt, 15 bytes

ðÊï æÈrõ xgU ¶V

Try it

ðÊï æÈrõ xgU ¶V :Implicit input of digit array U and integer V
ð :0-based indices of elements of U that are truthy under
 Ê : Factorial
 ï :Cartesian product with itself
 æ :First element/pair that returns true when
 È :Passed through the following function
 r : Reduce by
 õ : Inclusive range
 x : Reduce by addition after
 gU : Indexing each into U
 ¶V : Is equal to V?

Answer 9

Perl 5 List::Util, 82 bytes

sub{$s=pop;($i,$j)=($_%@_,int$_/@_),$s-sum(@_[$i..$j])||return($i,$j)for 0..@_*@_}

Try it online!

• Nahuel Fouilleul: -13 bytes using nested for syntax
• Nahuel Fouilleul: otherwise another 71 bytes with a regex, if 1-based indexing accepted for the end
• Kjetil S: @NahuelFouilleul – I was sure one for would be shorter than two. But there you go :-)
• Kjetil S: @NahuelFouilleul – Nice, I thought about regex but not this inner (??{}) magic. Your answer can be shortened to 62 bytes.

Answer 10

Pyth, 18 bytes

KEhfqQs:KhTheT^UK2

Try it online!

Takes n, sequence as separate inputs. Outputs [start, end] or an index error if no sequence exists.

Explanation

 # implicitly assign Q = eval(input())
KE # assign K = eval(input())
 ^ 2 # cartesian product of two copies of
 UK # range(len(K))
 f # filter this on lambda T
 s # sum of
 :KhTheT # slice K from first element of product to second element plus 1
 qQ # equals Q
 h # take the first element (this will give us the indices if they exist or an index error if they don't)

Answer 11

Jelly, 12 bytes

Jṗ2r/ị3S=ʋƇḢ

Try it online!

Full program, that takes a list of digits and an integer \$n\$, and outputs the 1-indexed indices, or 0 if there's no solution.

How it works

Jṗ2r/ị3S=ʋƇḢ - Main link. Takes a list of digits D on the left, and n on the right
J - Indices; [1, 2, ..., len(D)]
 ṗ2 - Cartesian square
 ʋƇ - Filter the indices on the dyad f([i, j], n):
 r/ - Range; [i, i+1, ..., j-1, j]
 ị3 - Index into D
 S - Sum
 = - Does that equal n?
 Ḣ - Take the first pair, or zero if there's no solution

Answer 12

C (clang), ^{(削除) 90 (削除ここまで)} 88 bytes

i;j;a;f(*s,n){for(a=i=-1;s[++i]*a;)for(a=n,j=i;a*s[j];)a-=s[j++]-48;*s++=!a*i-1;*s=j-1;}

Try it online!

Saved 2 bytes thanks to ceilingcat!!!

Inputs a pointer to a wide charater string of the sequence and \$n\$.
Returns the first and last position in the array referenced by the input pointer or \$-1\$ if no sum exists.

Answer 13

Thunno, \$ 25 \log_{256}(96) \approx \$ 20.58 bytes

LRDZ!gAu1+:z0sAISz1=kAJ0~

Takes a list of digits, then a number. Outputs 0 if it doesn't find the subsequence.

Explanation

LRDZ!gAu1+:z0sAISz1=kAJ0~ # Implicit input
LR # range(len(input))
 DZ! # Cartesian product with itself
 g k # Filter for items where the following is truthy:
 Au # Dump the pair onto the stack
 1+ # Add one to the last one (because of how Thunno's range works)
 : # Range between the two numbers
 sAI # Indexed into 
 z0 # The first input (this will return a list)
 S # The sum of this list
 z1= # Equals the second input?
 AJ # After the filter, get the first item of the list
 0~ # If the list was empty, push 0

Screenshots

Screenshot 1 Screenshot 2

Answer 14

Desmos, 79 bytes

L=[1...l.length]
T=[0^{(l[I...E].total-s)^2}(I,E)forE=L,I=L]
f(s,l)=T[T.x>0][1]

\$f\$ returns a point (I,E) that has the starting index I and the ending index E as the \$x\$ and \$y\$ coordinates, respectively, and returns the answer one-indexed.

For no solution, \$f\$ returns the point (undefined,undefined).

Note that because of the limitations of Desmos, this will not work for input lists longer than \100ドル\$ elements.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 15

C (clang), 76 bytes

Takes a list of digits and a number as input and returns \$[start, end)\$.

i;j;f(*l,s,n){for(i=j=0;n<0|s/~j*n;)n-=n>0?l[j++]:-l[i++];l[1]=j;*l=n?-1:i;}

How it works

i;j; // start and end of the sliding window, respectively.
f(*l, s, n) { // input a list of integers, its size and the number.
 for( // main loop
 i = j = 0; // start with i = 0 and j = 0 (empty window)
 n < 0 | // the sum of elements in the window exceeds n, we will remove elements in the next iteration
 s / ~j * n;) // j < l and the sum of elements does not match n
 n -= // subtract from n:
 n > 0 ? // if n > 0 ...
 l[j++] // increase the window size.
 : // else (n < 0) ...
 -l[i++] // decrease the window size.
 ; // end main loop
 l[1] = j; // l doubles as return placeholder. l[1] is the end of the window.
 *l = // l[0] is:
 n ? // if n != 0 ...
 -1 // there was no solution, set it to -1.
 : // else (n == 0) ...
 i; // we found the solution, set it to the start of the window.
}

Try it online!

Answer 16

Julia, (削除) 69 (削除ここまで) (削除) 65 (削除ここまで) 47 bytes

~=:;y^x=argmax(k->sum(x[k])==y,(q=keys(x)).~q')

Attempt This Online!

Uses 1-based indexing. Prints the range 1:1 if no solution exists.

• -4 bytes thanks to MarcMush: Replace 1:length(x) with keys(x)

• -18 bytes (!!) thanks to MarcMush: Improve range generation

• MarcMush: You can use keys instead of 1:length
• MarcMush: 47 bytes

Answer 17

Charcoal, 25 bytes

NθI⌊ΦEη⟦κ⌕EηΣ✂ηκ⊕μ1θ⟧⊕↨ι0

Try it online! Link is to verbose version of code. Outputs None if there is no solution. Explanation:

Nθ First input as a number
 η Second input
 E Map over digits 
 κ Current index
 η Second input
 E Map over digits
 η Second input
 ✂ 1 Sliced from
 κ Outer index to
 μ Inner index
 ⊕ Incremented
 Σ Take the sum
 ⌕ Find index of
 θ First input
 ⟦ ⟧ Make into list
 Φ Filtered where
 ↨ι0 Last element
 ⊕ Is not `-1`
 ⌊ Take the minimum (first if it exists)
 I Cast to string
 Implicitly print

Answer 18

Factor + math.combinatorics math.unicode, 69 bytes

[| n s | s length iota 2 [ last2 s subseq Σ n = ] find-combination ]

Try it online!

Returns a 0-based start index and 1-based end index. Returns f if there is no solution.

Answer 19

C99:

int main() {
 int x = 22;
 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, n = sizeof(a) / sizeof(int);
 
 int i = 0, j = 0, s = 0;
 while ((s < x && j < n) || (s > x && i < n))
 s += s < x ? a[j++] : -a[i++];
 printf("found: %d, i: %d, j: %d", s == x, i, j - 1);
 return 0;
}

The algorithm actually takes 66 bytes:

inti=0,j=0,s=0;while((s<x&&j<n)||(s>x&&i<n))s+=s<x?a[j++]:-a[i++];

Try it!

Answer 20

Haskell, 71 bytes

x#y=take 1[[s,e]|i<-[[0..length x-1]],s<-i,e<-i,sum[x!!i|i<-[s..e]]==y]

Try it online!

Haskell, 77 bytes

x#y=take 1[[s,e]|let m=length x-1,s<-[0..m],e<-[s..m],sum[x!!i|i<-[s..e]]==y]

Try it online!

Answer 21

Ruby, (削除) 58 (削除ここまで) 56 bytes

Returns nil if no subsequence is found.

-2 bytes thanks to Value Ink

->n,a{(b=*0...a.size).product(b).find{a[_1.._2].sum==n}}

Attempt This Online!

• Value Ink: Skip the brackets; (b=*0...a.size) works just fine.

Answer 22

Dyalog APL, (削除) 39 (削除ここまで) 33 bytes

Takes the sum on the left and the sequence of numbers on the right.

{⊃⍸⍺={+/s⌷⍨⊂(⍺-1)↓⍳⍵}/ ̈∘.,⍨⍳≢s←⍵}­⁡​‎‎⁡⁠⁢⁤⁢‏⁠‎⁡⁠⁢⁤⁣‏⁠‎⁡⁠⁢⁤⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁣⁤‏⁠‎⁡⁠⁢⁤⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏⁠‎⁡⁠⁢⁣⁢‏⁠‎⁡⁠⁢⁣⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌­
 s←⍵ # ‎⁡Save right arg in (s)equence
 ⍳≢ # ‎⁢Get range 1..length of s
 ∘.,⍨ # ‎⁣Outer product concat to get all start and end pairs
 { }/ ̈ # ‎⁤Apply over each
 ⍳⍵ # ‎⁢⁡ Get 1..right arg
 (⍺-1)↓ # ‎⁢⁢ and drop one less than left arg
 s⌷⍨⊂ # ‎⁢⁣ Select from the original sequence
 +/ # ‎⁢⁤ and sum
 ⍺= # ‎⁣⁡See which equal the left arg
 ⍸ # ‎⁣⁢Get its coordinate.
 # ‎⁣⁢The row will represent the starting point and the column the ending point of the subsequence
 ⊃ # ‎⁣⁣Disclose
💎

Created with the help of Luminespire.

Answer 23

APL(NARS), 42 chars

{0=c←↑⍸⍺={+/m[⍵]} ̈ ̈../ ̈k←,⍳,⍨≢m←⍎ ̈⍵:⍬⋄c⊃k}

Input in the right [⍵] one array of integers chars, in the left [⍺] a positive number, output one array of numbers.

All 1-indexed. If no solution it return the void list zilde.

It would make all possible ≢m x ≢m index ( ⍳,⍨≢m) of the tranlslate from ⍵ numeric array m, call it k, make ranges on element of k, apply these ranges on m and sum them, check alpha on them, c is the first index where sum is alpha. If c is zero, no solution, else the solution will be c⊃k

Test:

 h←{0=c←↑⍸⍺={+/m[⍵]} ̈ ̈../ ̈k←,⍳,⍨≢m←⍎ ̈⍵:⍬⋄c⊃k}
 10 h '123456789'
┌2───┐
│ 1 4│
└~───┘
 32 h '444444444'
┌2───┐
│ 1 8│
└~───┘
 15 h '123456789'
┌2───┐
│ 1 5│
└~───┘
 33 h '444444444'
┌0─┐
│ 0│
└~─┘
 17 f '123456789'
┌2───┐
│ 8 9│
└~───┘
 24 f '123456789'
┌2───┐
│ 7 9│
└~───┘

Answer 24

Arturo, 79 bytes

$[n,a][l:-size a 1loop 0..l'x[loop x..l'y[if n=sum slice a x y->return[x,y]]]0]

Try it

Returns [start end+1] or 0 if there's no solution.

Answer 25

Scala, 91 bytes

Golfed version. Try it online!

(a,t)=>a.indices.flatMap(s=>(s until a.length).filter(e=>a.slice(s,e+1).sum==t).map((s,_)))

Ungolfed version. Try it online!

object Main {
 def findSubarrays(arr: Array[Int], target: Int): Seq[(Int, Int)] = {
 for {
 start <- arr.indices
 end <- start until arr.length
 if arr.slice(start, end + 1).sum == target
 } yield (start, end)
 }
 def main(args: Array[String]): Unit = {
 val numbers = "12345".map(_.asDigit).toArray
 val target = 12
 println(findSubarrays(numbers, target))
 }
}