Count Customers Who Did Not Get A Computer

Easy
0/40
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
AdobeUrban Company (UrbanClap)

Problem statement

Mr. X runs an internet cafe which has 'K' computers. His internet cafe has 'N' customers who can come anytime throughout the day. Initially, all the 'K' computers are available for customer use. When a customer enters the cafe he first checks whether any available computer is there. If he finds one he starts using it and it is marked unavailable. When he leaves the cafe that computer is again marked as available. If the customer is not able to find any available computer he leaves the cafe immediately.

You are given an integer array ‘ARR’ in which each value occurs exactly 2 times, the index of the first occurrence of any value denotes the arrival time of the customer while the second occurrence denotes the departing time of the customer. Your task is to find the no. of customers who were not able to find any available computer and had to leave the cafe immediately.

For example : 
Consider the sequence of customers as [ 1, 2, 3, 2, 3, 1 ] for N = 3 and K = 2.

The procedure takes place as follows :
1) At the start, Customer 1 comes and finds an available computer and starts using it and now the number of available computers is reduced by 1. 

2) Customer 2 comes and he is also able to find an available computer and he starts using the computer. Now all the computers are unavailable.

3) Customer 3 comes and goes back immediately as there are no computers available currently. 

4) Customer 2 leaves the cafe making 1 computer available. 

5) As customer 3 has already left no new computers are made available.

6) Customer 1 leaves the cafe and all the computers are again available. 

As only Customer 3 was unable to find any available computers therefore the answer is 1 for this case.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer 'T', denoting the number of test cases.

The first line of each test case contains two space-separated integers 'N' and 'K' denoting the number of customers and the number of computers available in the cafe respectively.

The second line of each test case '2*N' space-separated integers denoting the array 'ARR'.
Output Format : 
For each test case print the number of customers who left the cafe without using a computer. Print the output of each test case in a new line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= 10^5
1 <= ARR[i] <= N

Time Limit: 1 sec
Sample Input 1:
2
2 2
1 2 2 1
3 2 
1 3 2 1 2 3
Sample Output 1:
0
1
Explanation for Sample Input 1:
For the first test case:
1) Initially, Customer 1 comes and finds an available computer and starts using it. Now only 1 computer is available.

2) Then Customer 2 comes and takes the only available computer. Now all computers are unavailable.

3) Customer 1 leaves the cafe making 1 computer available.

4) Customer 2 leaves the cafe making all the computers available.

As all customers were able to find an available computer and nobody left without using a computer. Hence, the answer is 0 in this case.

For the second test case : 
The procedure takes place as follows :
1) At the start, Customer 1 comes and finds an available computer and starts using it and now the number of available computers is reduced by 1. 

2) Customer 3 comes and he is also able to find an available computer and he starts using the computer. Now all the computers are unavailable.

3) Customer 2 comes and goes back immediately as there are no computers available currently. 

4) Customer 1 leaves the cafe making 1 computer available. 

5) As customer 2 has already left no new computers are made available. 

6) Customer 3 leaves the cafe and all the computers are again available. 

As only Customer 2 was unable to find any available computers therefore the answer is 1 for this case.
Sample Input 2:
2
4 1
1 2 3 4 4 3 2 1
2 2
1 2 1 2
Sample Output 2:
3
0
Hint

Try to think of an approach that stores the information about every customer in a data structure.

Approaches (1)
Solution using status array

The idea is to store the status of each customer in an extra array and use two variables availableComputers and customersWhoLeft that stores the number of available computers and the number of customers who left because of no available computers respectively.

 

The status of a customer can have 3 possible values. 

  • Status = 0, if the customer has not visited till now.
  • Status = 1, if the customer was able to find an available computer and is currently using it.
  • Status = -1, if the customer has left the cafe.

 

Steps :

 

  • If the number of computers is greater than or equal to the number of customers, then we will return 0 as in this case all customers will be able to find an available computer irrespective of the sequence with which they come and leave.
  • Initialize an array customerStatus having N+1 elements to store the status of each customer. Initialize all values with 0. As initially, no customer has visited the cafe. We are using N+1 elements as we are considering 1-indexing.
  • Set availableComputers as K and customersWhoLeft as 0.
  • Iterate from i = 0 to 2 * N - 1
    • If customerStatus [ARR[i]] is equal to 0 then
      • If availableComputers is greater than 0 then decrease availableComputers by 1 and set customerStatus[ARR[i]] as 1.
      • Otherwise, increase customersWhoLeft by 1 and set customerStatus[ARR[i]] as -1. We are setting the status as -1 here as the customer will leave the cafe immediately in this case.
    • Otherwise, If customerStatus [ARR[i]]  is equal to 1 then increase availableComputers by 1 and set customerStatus [ARR[i]] as -1. In this case, the customer has used the computer and has left the cafe after using it.
    • Otherwise, If customerStatus [ARR[i]] is equal to -1 then we do not have to do anything as the customer has already left the cafe.
  • Return customersWhoLeft as the final answer.
Time Complexity

O(N), where N denotes the number of customers.

 

As we are doing only one traversal of the input array having 2 * N elements. Hence, the overall Time Complexity is O(N).

Space Complexity

O(N), where N denotes the number of customers.

 

The number of elements in the customerStatus array is N. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Count Customers Who Did Not Get A Computer
Full screen
Console