Last Updated: 11 Mar, 2022
Hatori and Students
Easy
Hatori is the class teacher with 'N' students. He wants to select some students for the Republic Day parade. But out of all the students he chooses, the absolute difference of heights of any two students should not exceed 5.
He wants to pick the maximum number of students. Help him to know the maximum number of students he can choose.
For example:
Let the heights of students be 'H' = {1, 6, 7, 8, 2, 3, 11}. So at max, he can pick 4 students with heights: 6, 7, 8, and 11.
Input Format :
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains an integer 'N', denoting the size of the array of heights.
The following line contains 'N' space-separated positive integers that are the heights of students present in the class.
Output format :
For each test case, print one integer, i.e., the maximum number of students Hatori can pick.
Print the output of each test case in a new line.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= H[i] <= 10^9
Time Limit: 1 sec
Approaches
After sorting the heights of students in non-decreasing order, for every subarray, we can find whether this subarray can be of chosen students only. Then, we can select the subarray with the maximum size out of all possible subarrays.
Algorithm:
- Sort the given height array in non-decreasing order.
- Initialize a variable 'ANS' with 1. (We can always choose at least one student).
- Loop for 'i' from 0 to 'N' - 1.
- For every value of 'i' loop for 'j' from 'i' to 'N' - 1.
- Now, if 'H[j]' - 'H[i]' <= 5 and current value of answer is less than 'j' - 'i' + 1, then update 'ANS' to 'j' - 'i' + 1.
- For every value of 'i' loop for 'j' from 'i' to 'N' - 1.
- Return 'ANS'.
After sorting the heights of students in non-decreasing order, we need to pick a subarray such that the difference between the last and first element of this subarray is not more than 5.
For that, we can use two pointers, where the first pointer will point to the start of the subarray, and the second pointer will point to the end of the subarray we want to choose.
Now, if the difference between the heights of those pointers is more than 5, we need to decrease the difference so that we will move our first pointer forward.
Similarly, if the difference is less than or equal to 5, we can choose more students so that we will move our second pointer forward.
Whenever the difference is not more than 5, the maximum number of elements between these pointers will be the answer.
Algorithm:
- Sort the given 'H' array in non-decreasing order.
- Initialize a variable 'ANS' equals 1. (As we can always choose at least one student).
- Initialize two pointers 'P1' and 'P2' with 0.
- Now, while 'P2' is less than 'N'.
- If 'H[P2]' - 'H[P1]' > 5, increase 'P1' by 1.
- Else, update 'ANS' if 'ANS' < 'P2' - 'P1' + 1, and increase 'P2' by 1.
- Print 'ANS'.