CODEWITHSUNDEEP
arrayscombinationspermutationcombinatoricssub-array
Yash
Yash

Reputation: 77

What is the count of subarrays that will include a particular index 'i'?

Consider an array of 'n' elements, where ai is an element at index i where 1<=i<=N. I need to count the number of sub-arrays(contiguous sub-sequences of the array) that will include a particular index i. For example, consider, A = [1,2,3,4,5] The element 2 at index 2, will be included in 8 sub-arrays- {2},{1,2},{2,3},{1,2,3},{2,3,4},{1,2,3,4},{2,3,4,5},{1,2,3,4,5}.

Is there a way to frame a formula for this in terms of array size n and selected index i?

Upvotes: 2

Views: 1622

Answers (1)

RaffleBuffle
RaffleBuffle

Reputation: 5455

The number of sequences including index i is going to be equal to the number of sequences to the left of i times the number to the right. For both left and right we have to include the empty sequence.

In your example these would be:

left: {}, {1}
right: {}, {3}, {3,4}, {3,4,5}

Pairing each left sequence with every right sequence, with i in the center obviously, gives you the 8 sub-arrays in your example. (If you consider left and right above as sets then you're looking to form the Cartesian Product).

The number of left sequences is just i, the number on the right is n-i+1. The total is therefore i*(n-i+1).

Upvotes: 3

Related Questions