Expected number of evaluated nodes I have an array of zeroes with a length of $1024$. Suppose $n$ random elements are changed to $1$, the array now has $(1024-n)$ zeroes and $n$ ones.
I want to find the position of all $n$ elements that are $1$.
To do this I can sum all elements of an array.


*

*If the sum is greater than 0 I divide it by two down the middle (i.e. If sum of $A[1024]>0$ then I divide it in to two $512$ arrays).

*If instead the sum is $0$, this part of the array is set aside.


Now I want a formula to calculate the answer of the question "how many nodes should I evaluate to get that n elements?"  
P.S: I generated the code and got the average value with $10000$ times of generation and for example the evaluated nodes for $n=10$ is almost $137$.   
 A: I'll first restate what I understand to be the problem. You have a full binary tree of depth $k$ with $2^k$ leaves (in your case $k=10$), with exactly $n$ leaves uniformly randomly selected. You are looking for the expected number of evaluated nodes, where a node is regarded as evaluated if there is at least one selected leaf among the descendants of its immediate ancestor, or if the node is the root.
This problem can be solved using the linearity of expectation. The desired expected value is the sum of the probabilities of all nodes of being evaluated. A node at height $j$ (with $j=0$ for the leaves) is evaluated if one of $2^{j+1}$ leaves is set. The probability for this is
$$
1-\frac{\binom{2^k-2^{j+1}}n}{\binom{2^k}n}\;.
$$
There are $2^{k-j}$ such nodes. Then summing over $j$ yields the expected number of evaluated nodes:
$$
\sum_{j=0}^{k-1}2^{k-j}\left(1-\frac{\binom{2^k-2^{j+1}}n}{\binom{2^k}n}\right)+1\;,
$$
where I've added $1$ for the root separately since the formula isn't valid for $j=k$. For $k=n=10$, Wolfram|Alpha yields
$$
\frac{3059067866440075553278}{22512518015801599247}+1\approx136.883\;,
$$
in agreement with your numerical result.
