## 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: 1Explanation: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:2Explanation: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.

**Your Task: **

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 <= 10^{5}

1 <= i <= N

1 <= arr[i] <= 10^{5}

## Solution

class Solution{ public: int firingEmployees(vector<int> &arr, int n){ vector<int> adj[n+1]; 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; } adj[arr[i]-1].push_back(i); } vector<bool> prime(3*n, true); prime[0] = false; prime[1] = 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++; } for(auto it : adj[t]) { q.push({it,prevSeniorEmployees+1}); } } } return countOfBlackListedEmployees; } };

**write for us**page.