0

# Page Faults

Difficulty: MEDIUM
Contributed By
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

#### You have given a sequence of pages in an array ‘Pages’ of length ‘N’ and memory capacity ‘C’. You have to find the number of page faults using the Least Recently Used (LRU) Algorithm.

##### Input Format-
``````First-line contains an integer ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains two space-separated integers, ‘N’ and ‘C’.
The following line contains the array ‘Pages’ of the length ‘N’, denoting the sequences of the page.
``````
##### Output Format-
``````For each test case, print a single integer denoting the total number of page faults.
``````
##### Note :
``````You don’t need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints -
``````1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
0 <= ‘C’ <=  10^5
1 <= Pages[i] <= ‘N’, for 1 <= i <= ‘N’

Time Limit: 1 sec
``````
##### Sample Input-1
``````2
4 3
1 3 2 1
5 3
1 2 3 4 3
``````
##### Sample Output-1
``````3
4
``````
##### Explanation for Sample Input 1:
``````For test case 1:
Memory allocated with 3 pages, {1, 3, 2}. Hence total page faults = 3.
Page number ‘1’ is required, which is already present. Hence total page faults = 3 + 0 = 3.
For test case 2:
Memory allocated with 3 pages, {1, 2, 3}. Hence total page faults = 3.
Page number ‘4’ is required, So we replace LRU page ‘1’. Hence total page faults = 3 + 1 = 4.
Page number ‘3’ is required, which is already present. Hence total page faults = 4 + 0 = 4.
``````
##### Sample Input -2
``````2
9 4
5 6 1 3 2 4 1 6 5
7 3
1 2 1 4 2 3 5
``````
##### Sample Output -2
``````8
5
``````
Console