Table of contents

Introduction

Solution Approach

Algorithm -

C++ code:

Algorithm Complexity:

Key takeaways-

Last Updated: Mar 27, 2024

Ninja’s Messenger

Author Riya

Introduction

This section will discuss the problem “Ninja’s Messenger.” First, let’s see the problem statement.

Problem statement-

Ninja has a total of ‘N’ people in his community, numbered from 1 to N. He decided to build a messenger for the people of his community that can help the people to be connected among them. He has decided to make the following features in that messenger:

Log In and Log Out feature: Anyone can log in to the messenger to be online and log out of the messenger to be offline.
Add friend feature: A person ‘x’ can add another person ‘y’ as a friend.
Delete friend feature: A person ‘x’ can delete friendship between him and another person ‘y’, provided x and y are friends.
Count online friends feature: Using this feature, one can count his/her total number of currently online friends.

For implementing these features, he has decided to implement the following features for his messenger:

userLogIn(x): This will log in person ‘x’ and make him/her online
userLogOut(x): This will log out person ‘y’ and make him/her offline
addFriend(x, y): This will make persons ‘x’ and ‘y’ friends. Here friendship is mutual.
deleteFriend(x, y): This will unfriend the persons ‘x’ and ‘y’. Before calling this function, it is certain that ‘x’ and ‘y’ are friends.
onlineFriendsCount(x): This function will return the count of the number of friends of person ‘x’ who is online.

The task is to help Ninja in writing these functions to build the messenger.

We will be given ‘N,’ ‘M,’ where ‘N’ is the number of people in the community and ‘M’ is the number of pairs of friends that already exist. Also, we will be given a 2-D array F[M][2], such that F[i][0] and F[i][1] are friends initially where 0 <= i < M. Then, we will be given an ‘O’ representing the total number of persons who are online initially and an array ‘online[]’ containing the persons who are online.

Then we will be given a ‘Q’ number of queries. Each query will be any of the following forms:

{0, X}: In this query, we have to make person ‘X’ offline. It is certain that ‘X’ was online before the function call.
{1, X}: In this query, we have to make person ‘X’ online. It is certain that ‘X’ was offline before the function call.
{2, X, Y}: In this query, we have to make ‘X’ and ‘Y’ friends. It is certain that these two persons were not friends before the function call.
{3, X, Y}: In this query, we have to delete the friendship between ‘X’ and ‘Y .’It is certain that these two persons were friends before the function call.
{4, X}: In this query, we have to print the total number of friends of ‘X’ who are currently online.

Implement the required functions for the messenger, and for each query of type {4, X}, print the answer.

Check out Euclid GCD Algorithm

Solution Approach

This section will discuss the approach to implementing the messenger with the above features. The functions that we have to implement are already described in the previous section. The approach is to create a matrix data structure to store the friendship status between any two persons of the community and a boolean vector to store the online/ offline status of any person of the community. We will create a matrix ‘friendship[][]’ of size (N+1)*(N+1) in which if friendship[i][j] is equal to true, then i and j are friends else not. And also, we will create a boolean vector ‘isOnline[]’, in which if isOnline[i] is equal to true, then person ‘i’ is online, else offline. In this way, we can write all the functions discussed in the above section using these data structures.

Algorithm -

Step 1. First the main function. Inside the main function, create the following variables to store the given information.

N: Number of persons in the community
M: Number of pair of friends initially
F[M][2]: The pair of friends initially
O: Number of persons who were online initially
online[]: Persons who were online initially
Q: Number of queries given
queries[][] : Given queries

Step 2. Next, create a matrix ‘friendship[][]’ of size (N+1)*(N+1) to store the friendship status of each pair of persons in the community. If friendship[x][y] = true, then ‘x’ and ‘y’ are friends, else ‘x’ and ‘y’ are not friends. Mark the matrix elements true for each pair of persons who were friends initially.

Step 3. Next, create a vector ‘isOnline[]’ to store whether a person is online or offline. If isOnline[x] = true, then ‘x’ is online, else ‘x’ is offline. Mark the vector elements true for the persons who were given online initially.

Step 4. Then create functions ‘userLogIn()’ and ‘userLogOut()’ for log in and log out respectively. To log in a person ‘x,’ make him online by marking ‘isOnline[x] = true .’Similarly, to log out a person, make him offline by marking ‘isOnline[x] = false.’

Step 5. Then, create functions ‘addFriend()’ and ‘deleteFriend()’ to make friends and delete friendship, respectively. To make persons ‘x’ and ‘y’ friends, mark the corresponding cells in the matrix as ‘true .’Similarly, to unfriend persons ‘x’ and ‘y’, mark the corresponding cells in the matrix as ‘false.’

Step 6. Finally, create a function ‘countOnlineFriends()’ to count the number of friends of a person who is currently online. Inside the function, run a loop from 1 to N and check for each person if he is a friend and online.

C++ code:

#include <bits/stdc++.h>
using namespace std;


// Function to log in a given person
void userLogIn(int x, vector<bool>& isOnline)
{
	isOnline[x] = true;
}


// Function to log out a given person
void userLogOut(int x, vector<bool>& isOnline)
{
	isOnline[x] = false;
}


// Function to add friend
void addFriend(int x, int y, vector<vector<bool>>& friendship)
{
	friendship[x][y] = true;
	friendship[y][x] = true;
}


// Function to delete friendship
void deleteFriend(int x, int y, vector<vector<bool>>& friendship)
{
	friendship[x][y] = false;
	friendship[y][x] = false;
}


// Function to return the count of onlinr friends of a given persono
int onlineFriendsCount(int x, int N, vector<bool>& isOnline, vector<vector<bool>>& friendship)
{
	int count = 0;
	for(int i = 1; i <= N; i++)
	{
		if(friendship[x][i] == true && isOnline[i] == true) {
			count++;
		}
	}
	return count;
}

int main()
{

	// Number of persons in the community
	int N = 5;

	// Number of pairs of friends initially
	int M =3;
    	
	// Pairs of persons who are friends initially
	int F[M][2] = {{1, 3}, {2, 4}, {1, 5}};
    	
	// Number of persons who are online initially
	int O = 2;
    	
	// Array containing persons who are online
	int online[2] = {2, 4};
    	
	// Matrix representation of the friendship, Initially make all cell false, such that there is not friendship between any pair of persons
	vector<vector<bool>> friendship(N+1, vector<bool>(N+1, false));
    	
	// Vector to represent whether a person is online or offline, marking all person offline
	vector<bool> isOnline(N+1, false);
    	
	// Add the given initial friendship in the Adjacency matrix
	for(int i=0; i< M; i++)
	{
		int x = F[i][0], y = F[i][1];
   				
		// friendship is mutual
		friendship[x][y] = true;
		friendship[y][x] = true;
	}
    
	// Mark the persons online, who are initially online as given
	for(int i=0; i< O; i++)
	{
		int x = online[i];
		isOnline[x] = true;
	}
    	
	// Number of queries
	int Q = 5;
    
	// vector to store queries
	vector<vector<int>> queries;
    	
	// Query 1: {0, 2} = Log out person 2 and make him offline
	queries.push_back({0, 2});
    	
	// Query 2: {1, 3} = Log in person 3 and make him online
	queries.push_back({1, 3});
    	
	// Query 3: {2, 1, 4} = Make person 1 and person 4 friends
	queries.push_back({2, 1, 4});
    	
	// Query 4: {3, 1, 5} = Delete the friendship between person 1 and person 5
	queries.push_back({3, 1, 5});
    	
	// Query 5: {4, 1} = Count the friends of person 1 who are online
	queries.push_back({4, 1});
    
	// solve the queries
	for(int i=0; i<Q; i++)
	{
		int type = queries[i][0];
		if(type == 0) {
			int x = queries[i][1];

			// log out x
			userLogOut(x, isOnline);
		}
		else if(type == 1) {
			int x = queries[i][1];

			// log in x
			userLogIn(x, isOnline);
		}
		else if(type == 2) {
			int x = queries[i][1], y = queries[i][2];

			// Make x and y friends
			addFriend(x, y, friendship);
		}
		else if(type == 3) {
			int x = queries[i][1], y = queries[i][2];

			// delete friendship between x and y 
			deleteFriend(x, y, friendship);
		}
		else {
			int x = queries[i][1];

			// count the total friends of x who are online
			int count = onlineFriendsCount(x, N, isOnline, friendship);
			cout<<count<<endl;
		}
	}
    	
	return 0;
}

Output:
2

Algorithm Complexity:

Time Complexity: O(Q * N)

In the above implementation of messenger, the time complexity for the queries to make a person online or offline will be O(1), as making a person online/offline takes constant time. The time complexity of adding or deleting friendship will also be O(1) as it will also take constant time. The time complexity of counting online friends will be O(N) as we will loop through each person to check whether they are friends or not and whether they are online or offline. So, the worst-case time complexity will be O(Q * N), where ‘Q’ is the number of queries and ‘N’ is the number of persons in the community.

Space Complexity: O(N ^ 2)

In the above implementation of messenger, we have created a matrix of size (N + 1) * (N + 1) to store the friendship status for each pair of persons in the community. So, the space complexity of O(N^2).

Key takeaways-

This article discussed the problem “Ninja’s Messenger,” the solution approach to the problem, its C++ implementation, and its time and space complexity. If you want to solve more problems for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.