PROBLEM LINK:
DIFFICULTY:
SIMPLE
PREREQUISITES:
Math, Adhoc, Basic Algebra
PROBLEM:
Given Y papers to satisfy with atleast marks equal to median, find minimum marks to add to such papers so that given condition can be satisfied. If Y is greater than N, Dexter will be sad.
EXPLANATION:
Take the input of the marks in list/array such that A[i] denotes marks of ith paper.
Sort the list or array and find the median. Since N is always odd, in the list of 1, 2, …, N, (N/2 + 1)th position will be the median.
Since all the elements on the right side of the median, including median element will be already greater than or equal to median in the sorted array. So there will be N/2 + 1 papers already greater than or equal to median.
If N/2+1 is greater than or equal to Y, then print 0 since we have already satisfied the required condition. Else, start iterating from median element towards 1th index element (towards left from median).
Initialize the sum = 0, which will denote the marks required to make Y papers.
Find the difference of the every element with median and add it to the required sum until you get Y papers with marks greater than or equal to median.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here