Minimum Cost to Move Chips to The Same Position — Solution
Minimum Cost to Move Chips to The Same Position solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Cost to Move Chips to The Same Position is an easy coding problem on arrays, math and greedy, asked in Amazon, Adobe and Morgan Stanley interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Greedy
- Asked at: Amazon, Adobe, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are chips at various positions; position[i] is where the i-th chip sits. You may move any chip:
- by 2 in either direction, at cost
0; - by 1 in either direction, at cost
1.
Return the minimum total cost of gathering all the chips onto one position.
Example 1
Input: position = [1,2,3]
Output: 1
Explanation: Move the chip at 1 to 3 for free, then the chip at 2 to 3 for 1.
Example 2
Input: position = [2,2,2,3,3]
Output: 2
Example 3
Input: position = [1,1000000000]
Output: 1
Constraints
1 <= position.length <= 401 <= position[i] <= 1000000000
Hints for Minimum Cost to Move Chips to The Same Position
Hint 1
Moving by 2 is free, so a chip can reach any position of the same parity at no cost.
Hint 2
Gather every even chip onto one even square and every odd chip onto one odd square — still free.
Hint 3
Then one group has to step across, costing 1 per chip, so the answer is the size of the smaller group.
How to solve Minimum Cost to Move Chips to The Same Position
Moves of 2 are free, so all even-position chips can gather for free and so can all odd ones; then the smaller group crosses over at 1 per chip.
Approach
- Count chips at even positions.
- Return
min(even, total - even).
Why it works
Parity is the only invariant a free move cannot change; merging the two parity classes costs one unit per chip that changes parity, and moving the smaller class is cheapest.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The actual positions beyond their parity are irrelevant.
Reference solution
Python
def minCostToMoveChips(position) -> int:
even = sum(1 for p in position if p % 2 == 0)
return min(even, len(position) - even)Java
public static int minCostToMoveChips(int[] position) {
int even = 0, odd = 0;
for (int p : position) {
if (p % 2 == 0) even++;
else odd++;
}
return Math.min(even, odd);
}C++
int minCostToMoveChips(vector<int>& position) {
int even = 0, odd = 0;
for (int p : position) {
if (p % 2 == 0) even++;
else odd++;
}
return min(even, odd);
}JavaScript
var minCostToMoveChips = function(position) {
let even = 0, odd = 0;
for (let i = 0; i < position.length; i++) {
if (position[i] % 2 === 0) even++;
else odd++;
}
return Math.min(even, odd);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms