Program to find the number of persons wearing white hat - GeeksforGeeks

Program to find the number of persons wearing white hat - GeeksforGeeks
There are N persons in a room, each of them wearing a hat which is either black or white. Every person counts the number of other persons wearing the white hat. Given the number of counts of each person, the task is to find the number of persons wearing white hats, or print -1 if the given counts don't correspond to a valid situation.

There are only two kinds of persons. If each person counts correctly (valid situation), then the count value of each person wearing white hat is same. And also, the count value of each person wearing black hat is same. So there will be only one or two types of value in the array.
Let the number of white hats be i, 0 <= i <= N-1.
Now observe for each person wearing the white hat, the count value will be i – 1. So there will be i persons whose count will be i-1.
Also the number of persons wearing the black hats will be, N – i and their given count value will be i.
An interesting case is with zero white hats. If all values are 0, then everybody is wearing a black hat. Otherwise there can be at most one zero for the case when there is single person wearing a white hat. In case of one zero, all other entries must be 1.

Algorithm for solving this problem:

1. Count the frequency of each element of the array.
2. Since there are one or two types, say x and y.
   a) If the number of x's equal to x + 1 and number 
      of y's equal to n - y. The Number of hats equal
      to y or x + 1.
   b) Otherwise print -1. 

int numOfWhiteHats(int arr[], int n)

{

    // Counting frequencies of all values in given

    // array

    int freq[n+1];

    memset(freq, 0, sizeof(freq));

    for (int i=0; i<n; i++)

    {

        // Count of White hats cannot be more than

        // n for n persons.

        if (arr[i] >= n)

            return -1;

        freq[arr[i]]++;

    }

 

    // Counting number of different frequencies

    int diffFreq = 0;

    for (int i = n-1; i >= 0; i--)

        if (freq[i])

            diffFreq++;

 

    // Cases where all the persons wearing white hat.

    if (diffFreq == 1 && freq[n-1] == n)

        return n;

 

    // Case where no one wearing white hat.

    if (diffFreq == 1 && freq[0] == n)

        return 0;

 

    // Else : number of distinct frequency must be 2.

    if (diffFreq != 2)

        return -1;

 

    // Finding the last frequency with non zero value.

    // Note that we travers from right side.

    int k;

    for (k = n-1; k >= 1; k--)

        if (freq[k])

            break;

 

    // Checking number of k's must be n - k.

    // And number of (k-1)'s must be k.

    if (freq[k-1] == k && freq[k] + k == n)

        return freq[k-1];

    else

        return -1;

}

Read full article from Program to find the number of persons wearing white hat - GeeksforGeeks