1217. Minimum Cost to Move Chips to The Same Position
Model: qwen2.5-coder:14b
Topics: Array,Math,Greedy
FAANG asked: 0
Acceptance rate: 71.0%
Problem Breakdown
We are given an array position where each element represents the position of a chip on a number line. The goal is to move all chips to the same position with the minimum cost. Moving a chip by 2 positions (either forward or backward) has no cost, while moving a chip by 1 position incurs a cost of 1. We need to determine the minimum cost required to gather all chips at the same position.
Inputs:
position: An array of integers representing the initial positions of the chips.
Outputs:
- An integer representing the minimum cost to move all chips to the same position.
Implicit Constraints and Edge Cases:
- The array can be empty (though the problem states that
1 <= position.length). - Positions can be very large (
1 <= position[i] <= 10^9).
Intuition
A brute-force approach would involve trying all possible positions to move the chips to, calculating the cost for each scenario, and then choosing the minimum. However, this approach is inefficient due to its high time complexity (O(n^2) or worse).
The key insight is that moving a chip by 2 positions is free, which means we can effectively group chips at even positions together and chips at odd positions together without any cost. The only cost incurred is when moving chips from one group to the other. Therefore, the minimum cost will be the smaller count between the number of chips at even positions and the number of chips at odd positions.
Approach
-
Count Chips by Position Parity:
- Initialize two counters:
even_countandodd_count. - Iterate through the
positionarray. - For each position, check if it is even or odd.
- Increment
even_countif the position is even; otherwise, incrementodd_count.
- Initialize two counters:
-
Calculate Minimum Cost:
- The minimum cost to move all chips to the same position will be the smaller of
even_countandodd_count.
- The minimum cost to move all chips to the same position will be the smaller of
Complexity Analysis
- Time Complexity: O(n), where n is the length of the
positionarray. We iterate through the array once to count the chips at even and odd positions. - Space Complexity: O(1). We use a constant amount of extra space for the counters.
Solution
def minCostToMoveChips(position):
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)
Edge Cases Handled
- Single Chip: If there is only one chip, the cost will be 0 since no movement is needed.
- All Chips at Same Position: If all chips are already at the same position, the cost will be 0.
- Mixed Even and Odd Positions: The solution correctly calculates the minimum cost by comparing the counts of even and odd positions.