Number of sub-arrays with element included

Question

Suppose we have an array of numbers {x1, x2, x3 ...... xn}. If we select an element Xi from this array, how many sub-arrays exist with this element included?

Contiguous. I think sub-array implies that. Non-contiguous would probably be a subsequence — Omar S, Sep 01 '19 at 06:16
Don't use ${ \ldots }$ for (finite or infinite) sequences. Use $( \ldots )$ instead. Also, use MathJax to format your posts. — parsiad, Sep 01 '19 at 06:26

parsiad · Accepted Answer · 2019-09-01T06:25:53.467

1

Any contiguous subarray looks like $(x_a,x_{a+1},\ldots,x_{i-1},x_i,x_{i+1}\ldots,x_{b-1},x_b)$ where $a\leq i\leq b$. That gives you $i$ ways to choose $a$ and $n-i+1$ ways to choose $b$. Take the product to get $i(n-i+1)$ subarrays.

edited Sep 01 '19 at 06:25

answered Sep 01 '19 at 06:19

parsiad

25,154

Is n the length of the whole array? – Omar S Sep 01 '19 at 06:24
Yes, that's how you used it. – parsiad Sep 01 '19 at 06:25

Number of sub-arrays with element included

1 Answers1