Difficulty: Easy | Acceptance: 72.90% | Paid: No Topics: Array, Math, Greedy
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[x] to:
- position[x] + 2 or position[x] - 2 with cost = 0.
- position[x] + 1 or position[x] - 1 with cost = 1.
Return the minimum cost needed to move all the chips to the same position.
- Examples
- Constraints
- Parity Count Approach
- Mathematical Approach
Examples
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 is 2.
Example 3:
Input: position = [1,1000000000]
Output: 1
Constraints
1 <= position.length <= 100
1 <= position[i] <= 10^9
Parity Count Approach
Intuition Moving chips by 2 positions costs nothing, so all chips at even positions can be grouped together for free, and all chips at odd positions can be grouped together for free. The only cost is moving between parity groups.
Steps
- Count the number of chips at even positions
- Count the number of chips at odd positions
- Return the minimum of these two counts (we move the smaller group to the larger group)
class Solution:
def minCostToMoveChips(self, position: list[int]) -> int:
even_count = 0
odd_count = 0
for pos in position:
if pos % 2 == 0:
even_count += 1
else:
odd_count += 1
return min(even_count, odd_count)Complexity
- Time: O(n) where n is the length of position array
- Space: O(1) only using constant extra space
- Notes: This is the optimal solution with linear time complexity.
Mathematical Approach
Intuition Since we only care about parity (even or odd), we can use mathematical operations to count chips at each parity without explicit loops.
Steps
- Use reduce or sum to count even and odd positions
- Return the minimum count
class Solution:
def minCostToMoveChips(self, position: list[int]) -> int:
even_count = sum(1 for pos in position if pos % 2 == 0)
odd_count = len(position) - even_count
return min(even_count, odd_count)Complexity
- Time: O(n) where n is the length of position array
- Space: O(1) only using constant extra space
- Notes: Similar to the parity count approach but uses functional programming constructs.