PROBLEM LINK :
Author : Yash Mehta
Tester : Raghu Raman
Editorialist : Yash Mehta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Divide and Conquer Approaches, debugging skills
PROBLEM:
We are given the marks of N students of a class. We are supposed to print a frequency array of all the non-zero marks of the class and find the maximum frequency, or, mode of the distribution (the highest number of students who get the same marks).
SOLUTION (FROM SCRATCH) :
First, we make a frequency array of length 101 (each corresponding to an integral value of marks from 0 to 100). Scan through the input array of marks and increment the corresponding indices of the frequency array to get the number of students at all the marks (trivial frequencies included). Now, scan through this frequency array to detect the non-zero frequencies and store them in another array. This new array will be our unimodal array, that is, it will strictly increase and strictly decrease, with a single maxima somewhere in between, the start, or the end (the extreme cases of maxima appearing in the very beginning and the very end have been put just to test your debugging skills).
One part of the job is done (you can now simply print the unimodal array). For finding the single maximum element of this unimodal array, of course you can do the brute force approach of scanning through all the indices and see where x[i-1] < x[i] > x[i+1]. This will take time complexity O(n). We can find the maxima in O(log(n)) using Divide and Conquer approach, harnessing the fact that it is a unimodal array.
Strikingly similar to Binary Search, we first consider the middle of the array. If the middle element of the array is in the increasing part of the array (check by comparing with it’s neighbour), we recursively search the right half. If it’s in the decreasing part, we recursively search the left half. Refer to the code for clarity.
POINTS WHERE DEBUGGING WAS NECESSARY :
With reference to the incorrect code provided in the problem statement (link given below as well), following are the corrections that should have been made :
-
Line 5 : < should be replaced by \leq (necessary for an extreme case ! Think why…)
-
Line 12 : \leq should be replaced by \geq (The right half has to be searched if the if loop gives the condition for ‘mid’ being in the increasing part of the array, not decreasing as given)
-
Lines 36, 42 and 50 : The frequency array has 101 elements, not 100
-
Line 36 : All elements of the frequency array MUST be initialized to 0. We don’t want garbage values.
-
Line 56 : The condition for incrementing h has to be inside the if condition naturally.
-
Line 64 : We need to add a condition for an extreme case before straightaway printing the mode. If the mode is at the end of the array, simply printing the answer found by the Divide and Conquer approach will print one element left of the actual answer. We will have to add a condition that if the element we found is still smaller than the element to it’s right, we print the element to the right (of course, this would never be true in a general case since the answer found would always be the maximum if the unimodal array’s maxima lies in between (or even at the start) but at the end, there’s a small fallacy we need to take care of in this way.
LINK TO CODES (in C++):
NOTE : Debugging may be unique to the individuals. The correct code given above is just how the author debugged it in a way which has the as less editing as possible (with respect to the buggy code) according to the author. There may be some of you who may have debugged this with less editing, in which case, kudos !