- Observation 1 - There can be n final positions at max, all that matters is if a position is possible or not, if a position corresponding to an element is possible, then that element will never move from its place.
- Observation 2 - If our final position corresponds to an element
aj, the all
ai <= aj will for sure move to this position trivially.
if a < = b implies a < = 2*b
- Observation 3 - If the position corresponding to an element is possible, then all the positions corresponding to values greater than that element will also be possible. Now all we need to find is the smallest element corresponding to which the mentioned operation in the question is possible.
We will sort the array
arr and take prefix sum. It is obvious that for the last element the answer is always possible (from observation 2). We will have a pointer
pt from the second last element and check if
2*prefix[pt] >= arr[pt+1] then move the pointer one step lower to the next smaller element, i.e
pt--. If we can reach the element at pt, then we can reach the next element as well, which is understood from the condition we check before moving the pointer. We check
2*prefix[pt] because we know from observation 2 that all smaller elements can reach here trivially and then value will sum up till that position.
In the end we will get the number of elements for which we can reach a single element, hence all position corresponding to this element will be the positions which can be reached, and the final answer would hence be the number of elements from which we can use the mentioned operation to reach a single element.
for(int i = n-2; i>= 0; i--)
if(2*prefix[i] >= arr[i+1])
ans = n - i - 1;