Subtract from every value, so the initial values are . If , apply the reflection ; hence assume .
Let , , , , and . The final value must be the global average . After any number of operations, every reduced denominator is a power of two, so the task is impossible if is not a power of two.
Assume that is a power of two. Since , we have . Let . The minimum number of operations is .
Construction
If , then is odd. Make groups of size , each containing copies of , respectively. Split the remaining elements into groups of size .
Bound
Build a graph by joining two indices if they are ever used together, and let be its number of connected components. If a component has size , its final sum must be an integer, so is divisible by . Write the component sizes as ; then .
The total time complexity is .
Solution written by GPT5.6
If a size- group contains copies of , then its numbers of must be , , . Thus , and the sum of over all size- groups must be . The definition of guarantees that this is possible.
Every group can be averaged in exactly its size minus one operations. A size- group consists of and has odd sum. Dividing every value of a size- group by gives a group with odd sum.
Consider a group of size with values in and odd sum . Construct the operations backwards. Initially imagine copies of the final average . From two equal current values , fix one position to an original integer and change the other backwards to . This reverses one averaging operation.
When there are active positions, let . Every active value has fractional part , so only and can occur. Let be the number of high values and pair equal values.
The next level has active positions. For each state , the possible numbers of still-unrestored 's form one integer interval. At , the states are and . The transitions above compute the intervals from small upward. Prefix and suffix minima and maxima process one level in time, and the sum of all level sizes is . During reconstruction, choose any transition whose next state remains feasible. Reversing the recorded backward operations gives exactly forward operations.
Let be the initial number of 's in component . Its sum is , so . Since is odd,
Hence . A connected component of size requires at least operations, so the total number of operations is at least