Similar Heights solution codechef
Chef is teaching his class ofstudents at Hogwarts. He groups students with the same height together for an activity. Some of the students end up in a groups with only themselves and are saddened by this.
With the help of his magic wand, Chef can increase the height of any student to any value he likes. Now Chef wonders, what is the minimum number of students whose height needs to be increased so that there are no sad students?
- The first line of input will contain a single integer , denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains one integer — the number of students.
- The second line consists of space-separated integers denoting the heights of the students.
For each test case, output on a single line the minimum number of students whose heights must to be increased.
- The sum of over all test cases won’t exceed .
Sample Input 1
4 4 1 2 1 2 4 1 2 2 2 3 1 1 1 5 1 2 3 4 5
Sample Output 1
0 1 0 3
Test case: The students form groups each having students so no change of heights is required.
Test case: Initially the student with height cannot be paired with anyone else. Chef can increase his height to and now there is only group with all the students in it.
Test case: All students have same height and hence no change of heights is required.
Test case: One possible way is to increase the height of the first student to and the heights of the second and third students to , hence forming one group of students and one of students. In total, the heights of students need to be changed.