PROBLEM LINK:
Author: Bipin B
Editorialist: Rushang Gajjal
DIFFICULTY:
EASY
PROBLEM:
Results of N students were displayed as “Pass” or “Fail” behind their backs.
A student cannot see his/her result but can see everyone else’s results. Each of N students counts the number of passed students they can see. These counts are given as input. We have to output the number of students who failed or return -1 if there is some inconsistency in the input.
EXPLANATION:
Let’s take an example. Consider 10 students, out of which 7 passed and 3 failed. So for the 3 students who failed the count of students who passed will be 7 while for the remaining 7 students the count would be 6 as they don’t know their own result. Similarly, let’s assume instead of 7 only 5 students passed. In the second case, for 5 students that failed the count will be 5 while for other 5 it will be 4.
From observation, we can generalize the results. If they are N students, out of which x passed then the count of students who passed w.r.t these x students would be x-1 and for the remaining N-x students if would be x.
So in the given input, there should be at most 2 different counts x and x-1 respectively. Let a,b be the occurrences of x and x-1 in the input.
There are a few conditions:
a + b = N Since there are only two distinct count values in the input array.
x + 1 = a
If there are more than 2 different counts there is some inconsisteny in input. If there are same counts let’s assume c for all the students then either all students passed or all students failed(i.e. as per our generalization either x = N or x = 0) so c = N-1 (x-1 is the count w.r.t to x passed students and here x = N) or c = 0.
Time Complexity:
O(n) per test case.