A community nursery keeps two parallel rows of potted plants, Row A and Row B, each holding exactly n pots in fixed numbered positions. Every pot carries a small tag stamped with an integer species code. The head gardener wants every pot in Row A to end up carrying the very same species code (the gardener may pick whichever code works best). For each pot in Row A whose current code does not already match the chosen target code, the gardener has two ways to fix it: swap its tag with a pot from Row B that is already stamped with the exact target code (each Row B pot can supply at most one tag this way, and using it costs nothing), or have a brand-new tag printed and stamped directly onto the pot, which costs 1 unit of budget. Given the codes currently on both rows, find the minimum total budget the gardener must spend, over every possible choice of target species code, so that all n pots in Row A carry that one code.
Line 1: a single integer n — the number of pots in each row. Line 2: n space-separated integers a[1..n] — the species codes currently on Row A, in position order. Line 3: n space-separated integers b[1..n] — the species codes currently on Row B, in position order.
A single integer: the minimum total budget needed.
Example 1
Input
4 1 2 1 3 2 2 3 1
Expected
1
Explanation
Row A is [1,2,1,3] and Row B is [2,2,3,1]. Choosing target code 2: three Row A pots (holding 1, 1, and 3) are not yet 2, but Row B has two pots stamped 2 available to swap in for free, leaving only one pot that must be freshly stamped at a cost of 1. No other target code does better, so the minimum budget is 1.
Example 2
Input
3 7 8 9 1 2 3
Expected
2
Explanation
Row A is [7,8,9] and Row B is [1,2,3] — the two rows share no species codes at all. Whichever candidate code the gardener picks, exactly one Row A pot already matches it while the other two do not, and Row B never has that exact code in stock to swap in for free, so both remaining pots must be freshly stamped. The minimum achievable budget is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →