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.
The main observation here is that moving chips from position p to p+2 or p-2 incurs no cost. Hence, the cost to align all chips into one position is essentially the cost of moving all odd-indexed chips to even positions or vice versa.
To achieve this, count the number of chips at odd positions and the number of chips at even positions. The minimum cost to move all chips to the same position is the lesser of the two counts.
This C solution iterates through each chip position and counts how many are at odd and even positions. The minimum of these two counts determines the cost to align all chips.
Time Complexity: O(n), where n is the number of chips.
Space Complexity: O(1) because only a fixed amount of extra space is used.
A similar but slightly varied approach leverages modular arithmetic to classify indices. As the cost is incurred when moving by an odd number of steps, the strategy remains to count parity of indices and work from there.
By using an array `count` to track counts of even and odd indices, this solution provides an efficient way to determine the minimum movement cost using basic arithmetic for index parity.
Time Complexity: O(n) for iterating through the list of positions.
Space Complexity: O(1), with fixed space used to track counts.
Move all chips at even indices to position 0, and all chips at odd indices to position 1, all at a cost of 0. Then, choose the position (either 0 or 1) with fewer chips and move these chips to the other position. The minimum cost required is the smaller quantity of chips.
The time complexity is O(n), and the space complexity is O(1). Here, n is the number of chips.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Counting Even and Odd Indices | Time Complexity: O(n), where n is the number of chips. |
| Use Modular Arithmetic | Time Complexity: O(n) for iterating through the list of positions. |
| Quick Thinking | — |
| 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. |
Minimum Cost to Move Chips to The Same Position | LeetCode 1217 | C++, Java, Python • Knowledge Center • 6,735 views views
Watch 9 more video solutions →Practice Minimum Cost to Move Chips to The Same Position with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor