# WEFRNDS - Editorial

Practice

Author: Mann Mehta

Tester: Vatsal Parmar

Editorialist: Jaymeet Mehta

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-1

Iteration-2

Iteration-3

Here 5th student have exactly (5/2=2) Friends

# TIME COMPLEXITY

Time Complexity is O(1) per test case.