a semi-hard problem on combinatory

Question

I ran into a nice interview question.

the problem is as follows:

We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding average of all possible $c_{ij}$ in this array. if 4 basic operation in math $(+,-,*,/)$ can be done in $O(1)$. the best algorithm can be works in $O(n)$.

And this is the solution here:

Suppose that some entry of the array has value $k$. What is its contribution to the average of the $c_{ij}$? It is counted in some $c_{ij}$ iff $i \leq k \leq j$. Out of the $\binom{n+1}{2}$ many $c_{ij}$'s, there are exactly $k(n+1-k)$ in which the entry is counted, therefore its contribution to the average is $$ \frac{k(n+1-k)}{\binom{n+1}{2}} \cdot k = \frac{2k^2(n+1-k)}{(n+1)n}. $$ Summing this over all values in the array, we obtain the desired $O(n)$ algorithm.

Anyone can describe me very easily how this formula is archived? small example or any intuitive and simple idea?

Answer 1

In order for the $k$ entry to be counted in $c_{ij}$, we must have $1\le i\le k$ and $k\le j\le n$. There are $k$ integers in the set $\{1,2,\ldots,k\}$ and $n-(k-1)=n+1-k$ integers in the set $\{k,k+1,\ldots,n\}$, so there are $k(n+1-k)$ pairs $\langle i,j\rangle$ such that the $k$ entry is counted in $c_{ij}$. It contributes $k$ to each of those sums $c_{ij}$, so altogether it contributes

$$k\cdot k(n+1-k)=k^2(n+1-k)$$

to the sum of all of the partial sums $c_{ij}$. Dividing this by the number of sums $c_{ij}$ gives us the contribution of $k$ entries to the sum of the partial sums $c_{ij}$.

There are $\binom{n}2$ partial sums $c_{ij}$ with $1\le i<j\le n$, and there are $n$ partial sums $c_{ii}$ with $1\le i\le n$, so there are altogether

$$\binom{n}2+n=\frac{n(n-1)}2+n=\frac{n(n+1)}2=\binom{n+1}2$$

partial sums $c_{ij}$.

Added example: Suppose that $n=4$, and the array is $\langle 3,2,4,1\rangle$. The $3$ contributes to $c_{ij}$ when $i\le 3\le j$, so the possible choices for $i$ are $1,2$, and $3$, and the possible choices for $j$ are $3$ and $4$. Thus, there are $k=3$ choices for $i$ and $4-(3-1)=2$ choices for $j$, for a total of $3\cdot 2=6$ possible pairs of $i$ and $j$: the $3$ contributes to $c_{13},c_{14},c_{23},c_{24},c_{33}$, and $c_{34}$. The $4$, on the other hand, contributes to $c_{14},c_{24},c_{34}$, and $c_{44}$; there are $4\cdot1=4$ of these, because there are $4$ choices for $i$ ($1,2,3$, and $4$) and only one choice for $j$ ($4$).

Answer 2

Each row in the array below represents a set of terms in one of the sums. So $n=4$ in this example, and the first row contains the term of $c_{11}$, the second row the terms of $c_{12}$, and so on until the last row which contains the term of $c_{44}$. $$ \begin{array}{ccccc} a_1\\ a_1 & a_2\\ a_1 & a_2 & a_3\\ a_1 & a_2 & a_3 & a_4\\ \hline & a_2\\ & a_2 & a_3\\ & a_2 & a_3 & a_4\\ \hline & & a_3\\ & & a_3 & a_4\\ \hline & & & a_4 \end{array} $$ The best way to do the sum is by columns, not rows. So the first column has $4$ copies of $a_1$, which we can think of as $1$ group of $4$. The second column has six copies of $a_2$, which we can think of as $2$ groups of $3$: a group where $a_1$ is the element of lowest index and a group where $a_2$ is the element of lowest index. Similarly, the third column has $3$ groups of $2$ copies of $a_3$: a group with $a_1$ as the element of lowest index, a group with $a_2$ as the element of lowest index, and a group with $a_3$ as the element of lowest index. Finally, the fourth column has $4$ groups each with $1$ copy of $a_4$.

Therefore you get $$ 1\cdot4\cdot a_1+2\cdot3\cdot a_2+3\cdot2\cdot a_3+4\cdot1\cdot a_4. $$

Added: I may have misinterpreted the question. I understood that there was an array, $[a_1, a_2, \ldots, a_n]$ and that the goal was to find the average of the sums \begin{align} &c_{1,1}=a_1\\ &c_{1,2}=a_1+a_2\\ &c_{1,3}=a_1+a_2+a_3\\ &\vdots\\ &c_{n-1,n-1}=a_{n-1}\\ &c_{n-1,n}=a_{n-1}+a_n\\ &c_{n,n}=a_n. \end{align} There are $\binom{n+1}{2}$ such sums, so the average would be \begin{align} \frac{1}{\binom{n+1}{2}}\sum_{1\le i\le j\le n}c_{ij}&=\frac{1}{\binom{n+1}{2}}\sum_{i=1}^n\sum_{j=i}^n\sum_{\ell=i}^j a_\ell\\ &=\frac{1}{\binom{n+1}{2}}\sum_{i=1}^n\sum_{\ell=i}^na_\ell\sum_{j=\ell}^n1\\ &=\frac{1}{\binom{n+1}{2}}\sum_{i=1}^n\sum_{\ell=i}^na_\ell(n+1-\ell)\\ &=\frac{1}{\binom{n+1}{2}}\sum_{\ell=1}^na_\ell(n+1-\ell)\sum_{i=1}^\ell 1\\ &=\frac{1}{\binom{n+1}{2}}\sum_{\ell=1}^na_\ell(n+1-\ell)\ell, \end{align} which is an $O(n)$ computation. These rearrangements of summation symbols are essentially the "sum by columns rather than by rows" idea in the example above.

It seems, however, that what was actually meant is that there is an array, $[b_1,b_2,\ldots,b_n]$ and that $c_{ij}$ is defined by $$ c_{ij}=\sum_{\ell=1}^n b_\ell\theta(b_\ell-i)\theta(j-b_\ell), $$ where $$ \theta(m)=\begin{cases}0 & \text{if $m<0$}\\ 1 & \text{if $m\ge0$.}\end{cases} $$ This could also be written as $$ c_{ij}=\sum_{\ell=1}^nf(i,j,b_\ell), $$ where $$ f(i,j,k)=\begin{cases}k & \text{if $i\le k\le j$}\\ 0 & \text{otherwise.}\end{cases} $$ This problem can be converted to the problem I solved in $O(n)$ time by initializing the array $[a_1,a_2,\ldots,a_n]$ so that every element is $0$. Then for each $b$ in $[b_1,b_2,\ldots,b_n]$ such that $1\le b\le n$, add $b$ to $a_b$. For example, if $n=4$ and $[b_1,b_2,b_3,b_4]=[6,4,2,2]$ then $[a_1,a_2,a_3,a_4]$ would, at the end of the process, equal $[0,4,0,4]=[0,2,0,1]\circ[1,2,3,4]$, where $\circ$ is the element-wise product. In general, at the end of the process we have $$ [a_1,a_2,\ldots,a_n]=[m_1,m_2,\ldots,m_n]\circ[1,2,\ldots,n], $$ where $m_k$ is the number of times $k$ appears in $[b_1,b_2,\ldots,b_n]$. Now proceed using the previous algorithm, which, as was said, is also $O(n)$.

If we combine this with the previous formula, we get that the average is $$ \frac{1}{\binom{n+1}{2}}\sum_{\ell=1}^nm_\ell\cdot\ell\cdot(n+1-\ell)\ell. $$ It's not necessary to use the multiplicities $m_\ell$; you can instead sum over the individual $b_k$, using the function $f$ to omit those that might be out of the interval $[1,n]$: $$ \frac{1}{\binom{n+1}{2}}\sum_{k=1}^nf(1,n,b_k)\cdot(n+1-b_k)b_k. $$ This is manifestly an $O(n)$ calculation.