Minimum Cost to Move Chips to The Same Position

Problem Description

We have n chips, where the position of the ith chip is position[i]. We need to move all the chips to the same position. In one step, we can change the position of the ith chip from position[i] to:

• position[i] + 2 or position[i] - 2 with cost = 0.
• position[i] + 1 or position[i] - 1 with cost = 1.

Return the minimum cost needed to move all the chips to the same position.

Key Insights

• Moving chips by an even distance (±2) incurs no cost, while moving by an odd distance (±1) incurs a cost of 1.
• The cost to move chips is determined by their parity (even or odd position).
• To minimize the cost, we can either move all chips to an even position or to an odd position.
• The minimum cost will be the lesser of the count of chips at even positions and the count of chips at odd positions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution can be approached by counting the number of chips at even positions and odd positions. The minimum cost will be the minimum of these two counts since moving all chips to the position of the majority (either even or odd) will result in the least total movement cost.

Steps:

1. Initialize two counters for even and odd positions.
2. Iterate through the list of positions:
   • Increment the even counter if the position is even.
   • Increment the odd counter if the position is odd.
3. Return the minimum of the two counters.

Code Solutions