A page replacement algorithm should minimize the number of page faults

Question

I'm currently reading about Page Replacement Algorithms and I find complex question for me.

Question is:

Page replacement algorithm should minimize the number of page faults.

Description:

We can achieve this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages associated with that frame. Then, to replace a page, we can search for the page frame with the smallest counter.

b) How many page faults occur for your algorithm for the following reference string with four page frames?

1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2

Answer 1

This is Problem 9.13 of Operating System Concepts. Using the least frequently used(LFU) page-replacement algorithm and decreasing the frequency by 1 for the removed page, using FIFO for pages with the same counted frequency will get the answer 14. Detail:

page-reference strings	1	2	3	4	5	3	4	1	6	7	8	7	8	9	7	8	9	5	4	5	4	2
* LFU	1	1	1	1	5			5	6	6	8			8				8	8	8		8
page faults = 14		2	2	2	2			1	1	7	7			7				7	7	7		7
			3	3	3			3	3	3	3			9				9	9	5		2
				4	4			4	4	4	4			4				5	4	4		4
* optimal	1	1	1	1	1				6	6	8			8					8			2
page faults = 11		2	2	2	5				5	5	5			5					5			5
			3	3	3				3	7	7			7					4			4
				4	4				4	4	4			9					9			9