 0

Page Faults

Difficulty: MEDIUM
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
2
4 3
1 3 2 1
5 3
1 2 3 4 3
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