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.


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 <= 105
1 <= i <= N
1 <= arr[i] <= 105

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
GeekyBeginners articles are written by software geeks like you. If you also would like to contribute to GeekyBeginners by writing paid articles, you can check the write for us page.

Leave a Comment