**Difficulty:**Medium
Pre-requisites: Divide and conquer
Problem link:
Contest problem link
Practice problem link
Problem: To find the stack image when merge sort is called.
Explanation:
This problem can be solved in two ways:
-
By simulating merge sort and printng
the calls made.
-
Using binary search:
In this approach the given size is divided into 2 parts using
mid=(L+R)/2;
if(mid>=N) //N is the index to be found
R=mid; //Shift the right pointer to middle i.e. index lies between middle and left
else
L=mid+1; //Shift the left pointer to middle+1 i.e. index lies between middle and right
Using the second one is more preferable.
Problem setter’s solution: SOLUTION
I am unable to understand what is the problem statement. Can anyone elaborate the question(problem statement)?
Problem: To find the stack image when mergesort(A,i,i)
is called from the driver function.
As explained in the editorial, there are 2 ways of solving the problem.
- You can simulate the
mergesort(A,start,end)
function when it is called from the driver function which in C/C++
is main()
function.
Solution Link: https://ideone.com/CCNxfV
- You can use binary search for the index
i
.
Solution Link: https://ideone.com/cB9q6X
Time Complexity: O(log (s-t)).
When you see the solution code, you will be able to understand the solution more clearly.
Thanks