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^9The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for iterating through the list of positions.
Space Complexity: O(1), with fixed space used to track counts.
| 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. |
Minimum Cost to Move Chips to The Same Position | LeetCode 1217 | C++, Java, Python • Knowledge Center • 6,238 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