Friends (Medium)

Computer Science Level 3

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

Clarifications :

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.

True False

2 solutions

Christopher Boo
May 23, 2016

The list after we sort by decreasing number of friends is

1	`8 8 7 6 5 4 3 3 1 1`

We would try to build a network of friendship based on the list above. Now, we only know the number of friends each person has, but the matching is all up to us. If one has $x$ friends, then we must be able to find $x$ people that has at least one available slot for a friendship, and reduce the available number of friendship by $1$ . If every number in the list can be reduced to $0$ , then the network exist.

The question now is how should we match . First, we consider the person who currently has the most number of friends (say $x$ friends), then we identify the remaining $x$ people who has the most number of friends and reduce them by $1$ . If we couldn't find $x$ available people, we conclude that we couldn't form the network. Look at how this algorithm affects the list :

8 8 7 6 5 4 3 3 1 1
0 7 6 5 4 3 2 2 1 0    # successfully matches the 1st person with other 8 people
0 0 5 4 3 2 1 1 0 0    # successfully matches the 2nd person with other 7 people
0 0 0 3 2 1 0 0 0 0    # successfully matches the 3rd person with other 5 people

Now, only the $5$ -th and $6$ -th person has remaining slots and others have fully matched. We couldn't find $3$ person to match with the $4$ -th person. Therefore, the network cannot be constructed.

The question is a little confusing since there are 11 numbers but you mention 10 friends. So what is the first number for?

Geoff Pilling - 5 years ago

There are 10 numbers, isn't it?

Christopher Boo - 5 years ago

Somehow on my phone the initial "1" doesn't show up separated from the rest. Looks much better on my computer... By the way, nice question!

Geoff Pilling - 5 years ago

@Geoff Pilling – Glad you enjoyed it. :)

Christopher Boo - 5 years ago

@Geoff Pilling – Thanks, Geoff. The initial "1" was actually the line number of the code. I have edited the problem to remove it.

Pranshu Gaba - 5 years ago

Paul Schellenberg
May 23, 2016

Graph problem: count the number people who gave an odd friend count.

There is an odd number of people who gave an odd friend count.

This number tells us that somebody lied because friendships come in pairs.

Actually, since the first "1" doesn't count, there is an even number of odd numbers, but there still isn't a possible network.

Geoff Pilling - 5 years ago

Friends (Medium)

2 solutions

0 pending reports