Friends (Hard)

A group of \(N\) people numbered \(1, 2, \dots, N\) are going to your house for a party. To not let anyone feels left out, you want to befriend the one with the least number of friends. To achieve that, you will ask each of them the question "How many friends do you have?" and note down their response. Before working out the details, you want to make sure that no one give false information. That is, there is at least one possible network of friendships that matches the responses.

Below is a list of responses taken from a group of 30 people. Coincidentally, the number of friends are in decreasing order. Output the first (leftmost) person whom answer must be false. That is, it is possible to generate a network based from the responses of those before him, but not after him. If it is possible to generate a network of friendship, put your answer as 0.

29 29 28 25 23 23 22 20 19 17 17 16 14 14 14 14 13 8 7 7 6 6 6 5 5 5 4 4 1 1


  • Friendship is mutual. If \(A\) is \(B\)'s friend, then \(B\) is \(A\)'s friend as well.

  • You are not counted as their friends at the moment.

  • The first person is indexed as 1.

You are encouraged to solve the Medium version of this problem first.


Problem Loading...

Note Loading...

Set Loading...