# GFG POTD: Firing Employees Problem of the day

## Problem Statement

Geek is the founder of Geek Constructions. He always maintains a black-list of potential employees which can be fired at any moment.

The company has N employees (including Geek), and each employee is assigned a distinct rank (1 <= rank <= N) at the time of joining. The company has a hierarchical  management such that each employee always has one immediate senior.

Geek has a strange and unfair way of evaluating an employees performance. He sums the employee’s rank and the number of seniors the employee has. If it is a prime number, the employee is put up on the black-list.

Given an array arr[] in order of the rank of company employees. For rank i, arr[i] represents the rank of the immediate senior of the employee with the ith rank. If geek’s rank is i, then arr[i] is always equal to 0 as there is no one senior to him. Find out the number of Black-Listed employees.

Note: The black-list can not contain Geeks name as he is the founder of the company and he is the one that makes the list.

Example 1:

```Input:
N = 4
arr[] = {0, 1, 1, 2}

Output: 1

Explanation:
The hierarchy is as follows

(Geek)
Rank 1
/   \
Rank 2     Rank 3
/
Rank 4

Performance = rank + number of seniors
Performance for rank 1 = not considered.
Performance for rank 2 = 2+1 = 3 (prime)
Performance for rank 3 = 3+1 = 4 (not prime)
Performance for rank 4 = 4+2 = 6 (not prime)
Therefore, only employee 1 is black-listed.```

Example 2:

```Input:
N = 3
arr[] = {2, 3, 0}

Output: 2

Explanation:
The hierarchy is as follows

(Geek)
Rank 3
/
Rank 2
/
Rank 1

Performance for rank 3 = not considered.
Performance for rank 2 = 2+1 = 3 (prime)
Performance for rank 1 = 1+2 = 3 (prime)
Rank 1 and 2 are both black-listed.```

You don’t need to read input or print anything. Your task is to complete the function firingEmployees() which takes the array arr[] and its size N as input parameters. It returns the number of black-listed employees.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 105
1 <= i <= N
1 <= arr[i] <= 105

## Solution

```class Solution{
public:
int firingEmployees(vector<int> &arr, int n){
int countOfBlackListedEmployees = 0;
int founder = -1;

map<int,int> mp;

for(int i = 0; i < n; i++) {
mp[i] = i+1;
if(arr[i]==0) {
founder = i;
continue;
}
}

vector<bool> prime(3*n, true);
prime = false;
prime = false;

for(int i = 2; i*i<=3*n; i++) {
for(int j = 2*i; j<=3*n; j+=i) {
prime[j] = false;
}
}

queue<pair<int,int>> q;
q.push({founder,0});

while(!q.empty()) {
int size = q.size();
while(size--) {
int t = q.front().first;
int prevSeniorEmployees = q.front().second;
q.pop();

if(t!=founder) {
int judingCriteria = mp[t] + prevSeniorEmployees;

if(prime[judingCriteria]) countOfBlackListedEmployees++;
}