1.
Introduction
2.
Solution Approach
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity:
6.
Key takeaways-
Last Updated: Mar 27, 2024

# Ninja’s Messenger

Riya
1 upvote

## 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:

1. 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.
2. Add friend feature: A person ‘x’ can add another person ‘y’ as a friend.
3. Delete friend feature: A person ‘x’ can delete friendship between him and another person ‘y’, provided x and y are friends.
4. 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:

2. userLogOut(x): This will log out person ‘y’ and make him/her offline
3. addFriend(x, y): This will make persons ‘x’ and ‘y’ friends. Here friendship is mutual.
4. deleteFriend(x, y): This will unfriend the persons ‘x’ and ‘y’. Before calling this function, it is certain that ‘x’ and ‘y’ are friends.
5. 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:

1. {0, X}: In this query, we have to make person ‘X’ offline. It is certain that ‘X’ was online before the function call.
2. {1, X}: In this query, we have to make person ‘X’ online. It is certain that ‘X’ was offline before the function call.
3. {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.
4. {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.
5. {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.

1. N: Number of persons in the community
2. M: Number of pair of friends initially
3. F[M][2]: The pair of friends initially
4. O: Number of persons who were online initially
5. online[]: Persons who were online initially
6. Q: Number of queries given
7. 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.

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

Live masterclass