---

1. Problem Summary

You are given an array position where each element represents the position of a chip on a number line.

You must move all chips to the same position, where movement cost rules are:

• Moving a chip by 2 positions (left or right) costs 0
• Moving a chip by 1 position costs 1

Your task is to compute the minimum total cost required to gather all chips at a single position.

Example interpretation:
If chips are at positions [1, 2, 3]:

• Move chip at 1 to 3: cost 0 (two steps)
• Move chip at 2 to 3: cost 1 (one step)
  Total cost: 1

---

2. Key Insights

Cost depends only on parity (even vs odd)

Because:

• Moving by 2 steps costs 0
• Moving between positions with same parity:
  • even → even
  • odd → odd
    always costs 0

Cost occurs only when switching parity

To gather chips together:

• If final position is odd:
  • all chips at even positions must move with cost 1 each
• If final position is even:
  • all chips at odd positions must move with cost 1 each

Therefore:

Total cost = minimum of:

(number of chips at even positions)
(number of chips at odd positions)

No need to simulate movements

Simply count parity groups.

---

3. Approach

Count parity groups and choose cheaper target

Steps:

1. Initialize counters: evenCount = 0 oddCount = 0
2. Loop through position:
   • if number is even → evenCount++
   • else → oddCount++
3. Return: Math.min(evenCount, oddCount)

This computes minimum switching cost.

---

4. Time and Space Complexity

Time Complexity: O(N)

Single scan through the array.

Space Complexity: O(1)

Only two counters used.

---

5. Java Solution

class Solution {
    public int minCostToMoveChips(int[] position) {
        int evenCount = 0;
        int oddCount = 0;

        for (int p : position) {
            if (p % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }

        return Math.min(evenCount, oddCount);
    }
}

---

6. Dry Run Examples

Example 1

Input:

[1, 2, 3]

Parities:
1 → odd
2 → even
3 → odd

Counts:
oddCount = 2
evenCount = 1

Minimum cost = min(2, 1) = 1

Output:

1

---

Example 2

Input:

[2, 2, 2, 3, 3]

evenCount = 3
oddCount = 2

Minimum cost = 2

Output:

2

Explanation:
Best to move odd chips to even positions (cost 2)

---

Example 3

Input:

[1, 1000000000]

1 → odd
1000000000 → even

evenCount = 1
oddCount = 1

Minimum cost = 1

---

Example 4

Input:

[4]

Only one chip → no movement needed

evenCount = 1
oddCount = 0

Answer = 0

---

Example 5

Input:

[3, 3, 3]

All odd → cost 0

---

7. Why This Solution Works

• Movement by 2 units is free
• Staying within parity group costs zero
• Only cross-parity moves incur cost
• Cheapest target parity minimizes cost
• No need for sorting
• No simulation required
• Always optimal by mathematical property

---

8. Common Mistakes

1. Trying to compute cost for each possible target position
2. Assuming distance magnitude matters (it doesn’t except parity)
3. Sorting unnecessarily
4. Treating problem like typical distance minimization (median/mean irrelevant)
5. Misunderstanding movement cost rules