Interview Questions/Coding/Parity Slot Repair

Parity Slot Repair

Preview mode. Log in to edit, run, submit, and save progress.

Easy

Parity Slot Repair

A device array is valid when every even zero-based index stores an even value and every odd zero-based index stores an odd value. One repair operation swaps any two values in the array. For each array, compute the minimum number of swaps needed to make it valid, or print -1 if the misplaced values cannot be paired into valid swaps. Input Format: The first line contains t, the number of test cases. Each test case contains n followed by n integers. Output Format: For each test case, print the minimum number of swaps, or -1 if repair is impossible.

Examples

Example 1

Input:

1
4
3 2 7 6

Output:

Explanation: Even indices 0 and 2 hold odd values, while odd indices 1 and 3 hold even values. Two swaps can pair those mismatch types.

Approach hint

Start with the simplest clear approach, explain the trade-off, then move toward the cleaner answer.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp