Friends (Medium)

Computer Science Level pending

A group of \(N\) people numbered \(1, 2, \ldots, 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 10 people. Answer True if it's possible to find a network of friendships that matches, False otherwise.

7 3 1 8 3 6 5 1 8 4


  • 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.

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


Problem Loading...

Note Loading...

Set Loading...