PROBLEM LINK
Author: Mann Mehta
Tester: Vatsal Parmar
Editorialist: Jaymeet Mehta
DIFFICULTY
Cakewalk
PREREQUISITES
Basic Math, Basic Graph Terminology's, Observation
PROBLEM
You are given a N denoting number of students in the class. Every ith students have i friends except the Nth student, our task is to calculate number of friends that Nth student have.
Here friendship is only possible in between N students of class.
EXPLANATION
Here the best approach is to visualise the friendship network of class. Where every node is denoted as student and it's degree it's denoted as number of friends that student have.
First of all let’s take N nodes, and start satisfying the degree of (N-1)th node, after this you find that degree of 1st node also satisfies.
And go for (N-2)th node, when you satisfies the degree of (N-2)th node, at that time also you will find that degree of 2nd node also satisfies.
Now, you have to go on till (N-N/2)th node and you will find that all the node have satisfies it’s degree.
At that time Nth node have exactly degree of N/2 it means that Nth student have exactly N/2 friends when every ith student of the class have i friends.
Let’s do it for N=5:-
-
At every iteration 2 nodes going to satisfies it’s degree. (N-I)th node and (I)th node, where (I) denote’s the iteration number
- At every iteration Nth node get one friendship.
Iteration-2
Here 5th student have exactly (5/2=2) Friends