A row of n signal beacons runs along a maintenance corridor, numbered 0 through n-1 from one end to the other. Each beacon i currently reports a status code, a non-negative integer a_i. Inspectors want the row of codes to read identically from either direction: the code reported by the beacon that is i positions from the left must exactly equal the code reported by the beacon that is i positions from the right, for every valid i (in other words, the sequence of codes must be a palindrome). A maintenance action flips exactly one bit of exactly one beacon's status code (changing that bit from 0 to 1 or from 1 to 0); every such flip, on any beacon and any bit, counts as one action. Determine the minimum number of maintenance actions needed to make the row of codes read the same from both ends.
Print a single integer: the minimum number of bit-flip actions required.
Example 1
Input
3 5 2 7
Expected
1
Explanation
There are 3 beacons; the outer pair is (a_0, a_2) = (5, 7). In binary 5 = 101 and 7 = 111, which differ in exactly one bit, so a single flip of that bit makes the outer pair match. The middle beacon a_1 has no partner to match, so it needs no changes. Total minimum actions: 1.
Example 2
Input
4 0 9 3 12
Expected
4
Explanation
There are two mirrored pairs: (a_0, a_3) = (0, 12) and (a_1, a_2) = (9, 3). In binary 0 = 0000 and 12 = 1100 differ in 2 bits; 9 = 1001 and 3 = 0011 also differ in 2 bits. Summing both pairs gives 2 + 2 = 4 minimum flip actions.
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 →