0

Page Faults

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

Problem Statement

In computing, a page fault is an exception for the memory management unit (MMU) when a process accesses a memory page without proper preparations. - Page Fault

Page replacement algorithm is needed to decide which page needs to be replaced when the new page comes in. Whenever a new page is referred to and is not present in memory, the page fault occurs, and the Operating System replaces one of the existing pages with a newly needed page.

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
Reset Code
Full screen
copy-code
Console