Code Implementation

class Solution:
    def minCostToMoveChips(self, position):
        even = sum(1 for x in position if x % 2 == 0)
        odd = len(position) - even
        return min(even, odd)
      

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int even = 0, odd = 0;
        for (int x : position) {
            if (x % 2 == 0) even++;
            else odd++;
        }
        return min(even, odd);
    }
};
      

class Solution {
    public int minCostToMoveChips(int[] position) {
        int even = 0, odd = 0;
        for (int x : position) {
            if (x % 2 == 0) even++;
            else odd++;
        }
        return Math.min(even, odd);
    }
}
      

var minCostToMoveChips = function(position) {
    let even = 0, odd = 0;
    for (let x of position) {
        if (x % 2 === 0) even++;
        else odd++;
    }
    return Math.min(even, odd);
};
      

Problem Description

You are given an array position where each element represents the position of a chip on a number line. You can move any chip by 2 units (to the left or right) at no cost, or by 1 unit (to the left or right) at a cost of 1 per move. Your task is to determine the minimum cost required to move all chips to the same position.

• There is always at least one valid solution.
• You may not "reuse" chips; each chip must be moved individually.
• All moves are counted per chip, and you choose the target position.

Thought Process

At first glance, this problem may look like it requires trying every possible target position and calculating the cost for each chip to move there. This brute-force method would work, but it could be inefficient for large inputs.

However, notice the special cost structure: moving a chip by 2 units costs 0, and only moves by 1 unit cost 1. This means moving chips between positions of the same parity (both even or both odd) is free, while moving between odd and even positions costs 1 per chip.

Therefore, the problem boils down to counting how many chips are on even positions and how many are on odd positions. The minimum cost is the smaller of these two counts, since you can move all chips from one parity to the other (odd to even or even to odd) at a cost of 1 per chip.

Solution Approach

• 1. Count Chips by Parity:
  • Go through the position array.
  • If a chip's position is even, increment the "even" counter.
  • If a chip's position is odd, increment the "odd" counter.
• 2. Calculate Minimum Cost:
  • The cost to move all chips to an even position is the number of chips on odd positions (since only they need to move and pay a cost).
  • The cost to move all chips to an odd position is the number of chips on even positions.
  • The answer is the smaller of these two numbers.
• 3. Return the Result:
  • Return min(even, odd) as the final answer.

This approach is efficient because it only requires a single pass through the array and simple counting.

Example Walkthrough

Let's use the input position = [1, 2, 3] as an example:

• Chip at position 1 (odd) → odd = 1
• Chip at position 2 (even) → even = 1
• Chip at position 3 (odd) → odd = 2

So, odd = 2, even = 1.

• To bring all chips to position 1 or 3 (odd), only the chip at position 2 needs to move, costing 1.
• To bring all chips to position 2 (even), the two chips at positions 1 and 3 need to move, costing 2.

The minimum cost is 1, which matches the output of the algorithm.

Time and Space Complexity

• Brute-force approach:
  • For each possible target position, sum the cost for every chip to move there. This is O(n²), where n is the number of chips.
• Optimized approach (parity counting):
  • Time Complexity: O(n), since we scan the array once.
  • Space Complexity: O(1), only two counters are used.

The optimized approach is much faster and uses constant extra space.

Summary

The key insight is recognizing that moving chips between positions of the same parity is free, and only moves between odd and even positions cost 1 per chip. By simply counting the number of chips on odd and even positions, we can directly compute the minimum cost to bring all chips to any single position. This makes the solution both elegant and efficient.