Watch 10 video solutions for Minimum Cost to Move Chips to The Same Position, a easy level problem involving Array, Math, Greedy. This walkthrough by Knowledge Center has 6,735 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: position = [1,2,3] Output: 1 Explanation: First step: Move the chip at position 3 to position 1 with cost = 0. Second step: Move the chip at position 2 to position 1 with cost = 1. Total cost is 1.
Example 2:
Input: position = [2,2,2,3,3] Output: 2 Explanation: We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost = 2.
Example 3:
Input: position = [1,1000000000] Output: 1
Constraints:
1 <= position.length <= 1001 <= position[i] <= 10^9Problem Overview: You get an array where position[i] represents the location of the i-th chip. Moving a chip by 2 positions costs 0, while moving it by 1 position costs 1. The task is to move all chips to the same position with the minimum total cost.
Approach 1: Counting Even and Odd Positions (O(n) time, O(1) space)
The key observation comes from movement cost. Moving a chip by 2 steps costs nothing, which means you can freely move between positions with the same parity (even → even or odd → odd). Cost only appears when switching parity. Iterate through the array once and count how many chips are on even positions and how many are on odd positions. If you move all chips to an even position, every chip currently on an odd position costs 1 to move. If you move everything to an odd position, every chip on an even position costs 1. The minimum cost is simply min(evenCount, oddCount). This greedy counting strategy works because all same-parity moves are free, so the only cost is flipping parity.
This approach uses simple iteration over the array and a greedy decision based on which parity group is smaller.
Approach 2: Use Modular Arithmetic (O(n) time, O(1) space)
The same idea can be expressed more mathematically using position[i] % 2. The modulo operation directly tells whether a position is even or odd. Iterate through the array and increment counters depending on the result of the modulo operation. Since moving by 2 preserves parity, all chips with the same modulo value can gather at one position for free. Chips with the opposite modulo require a single move costing 1. After processing the array, return the minimum of the two counts.
This formulation emphasizes the mathematical insight behind the problem and highlights the role of modular arithmetic. It leads to the same optimal greedy decision and requires only constant extra space.
Recommended for interviews: Interviewers expect the parity observation that moving by 2 is free. The optimal solution counts chips on even and odd positions and returns the smaller group size. Brute force simulations are unnecessary here. Demonstrating the parity insight quickly shows strong problem-solving and pattern recognition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Even and Odd Positions | O(n) | O(1) | Best general solution. Single pass with simple counters. |
| Modular Arithmetic (Parity Check) | O(n) | O(1) | When expressing the parity logic using mathematical reasoning. |