\n1) We sort the array so that we can calculate the median easily.<\/p>\n
2) We keep increasing the median to make it equal to its right values until it reaches the last element (largest value in array) or our operation limit is reached.<\/p>\n
3) After converting median to the current right value, we add the total number of steps for every element between the median and current right elements, which make value from median to right element equal, maintaining the non-decreasing behavior of array.<\/p>\n
4) Once capacity is reached or we reach the last element, we print array.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2020\/06\/Group-200@2x.png\")
<\/p>\n
\nLet array A<\/code> be,
\nand, capacity<\/code> is 2<\/code>, we sort array, so that we can get a non-decreasing sequence to find median, after sorting array, we get<\/p>\nMedian of an odd sized array is middle element of it’s non-decreasing form, so our current median lies at index 2<\/code>, i.e. our current median is 3<\/code>.<\/p>\nWe make current median equal to elements to it’s right, so total steps would be A[mid+1]-A[mid]<\/code>, i.e. 1 in current test case, so our final array becomes,<\/p>\nWe consumes 1 step in last step, so we’re left with only 1 capacity<\/code>.<\/p>\nNow, our median have become 4<\/code> and middle index and element at it’s right are same now. So, we move forward toward more right of middle index, i.e. index 4<\/code> at which 5<\/code> resides.<\/p>\nWe convert all values between median index and right index equal to the value to the current right index i.e. 5<\/code>, so total number of operations will be,<\/p>\noperations = (rightIndex - middleIndex) * (A[rightIndex]-A[middleIndex])<\/code><\/p>\noperations = (4-2) * (5-4)<\/code><\/p>\noperations = 2 * 1<\/code><\/p>\noperations = 2<\/code><\/p>\nTotal numeber of operation required are 2<\/code>, but we are left with only 1<\/code> capacity<\/code>, hence we skip this step, and print our current median because we cannot afford further step. So, our final median becomes 4<\/code>.<\/p>\n<\/blockquote>\nSolutions<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645174307817-Article_398.png\")
<\/p>\n