Along a rocky shoreline, n crabs are perched on numbered rocks that run 0, 1, 2, ... in a straight line, and rock pos[i] holds the i-th crab (several crabs may share the same rock). Every crab's natural gait lets it leap exactly two rocks in either direction at no energy cost, and it can also make a single one-rock leap that costs 1 unit of energy because it goes against that gait. A crab may chain as many free two-rock leaps as it wants together with at most the one-rock leaps it needs. The crabs want to end up all together on one common rock, which does not have to be one any crab started on. Find the minimum total energy needed for every crab to reach that common rock.
Line 1: a single integer n. Line 2: n space-separated integers pos[1..n].
A single integer: the minimum total energy needed to gather every crab on the same rock.
Example 1
Input
5 1 2 3 4 6
Expected
2
Explanation
Rocks 2, 4, and 6 are even (3 crabs); rocks 1 and 3 are odd (2 crabs). Gathering everyone on an even rock costs the two odd-rock crabs 1 unit each to flip parity, after which every crab can glide the rest of the way for free. Total energy = min(3, 2) = 2.
Example 2
Input
4 2 4 6 8
Expected
0
Explanation
All four crabs already sit on even rocks, so they can all glide via free two-rock leaps to any common even rock. Minimum energy = min(4, 0) = 0.
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 →