Question: BNY Mellon, Recently Asked Questions in IIT-G, November, 2022
0
Entering edit mode

Question 1

Merge Elements

Click here to Practice

1.11.21.31.4

ADD COMMENTlink 15 days ago John 450 • updated 8 days ago Manas 150
0
Entering edit mode

Question 1

  • 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.

Solution

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.

pseudo code:

for(int i = n-2; i>= 0; i--)
{
    if(2*prefix[i] >= arr[i+1])
        continue;
    else
    {
        ans = n - i - 1;
    }
}
ADD COMMENTlink 8 days ago Manas 150

Login before adding your answer.

Similar Posts
Loading Similar Posts