Minimum Cost to Move Chips to The Same Position
Problem Description
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:
1) position[i] + 2 or position[i] - 2 with cost = 0.
2) position[i] + 1 or position[i] - 1 with cost = 1.
Return the minimum cost needed to move all the chips to the same position.
Problem Explanation
Free Moves (Cost = 0)
A chip can move from one position to another when both positions have the same parity, meaning both positions are either even or both are odd. This move does not cost anything.
For example:
- Moving from position 2 to position 4: both are even, so it's a free move.
- Moving from position 3 to position 5: both are odd, so it's also a free move.
The reason these moves are free is that moving between even or between odd positions does not involve changing parity (even to odd or odd to even), and therefore, it doesn’t incur any cost.
Costly Moves (Cost = 1)
A chip will incur a cost of 1 when it moves from one position to another where the positions have different parities. This means moving between an even and an odd position will cost 1.
For example:
- Moving from position 2 to position 3: one is even, and the other is odd, so it costs 1.
- Moving from position 3 to position 4: one is odd, and the other is even, so it also costs 1.
These moves are costly because you are changing parity from even to odd or odd to even, which results in a cost of 1.
Example
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.
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.
Constraints
- 1 <= position.length <= 100
- 1 <= position[i] <= 10^9
Since we realized that moving between even or odd positions is free, but switching between them costs 1. Let's see how we can think in greedy way to come up with a linear solution.
Optimal Approach
Intuition
We can see that moving a chip from an even position to another even position, or from an odd position to another odd position, doesn’t cost anything. But moving between even and odd positions will always cost 1.
So, the core idea here is to figure out how many chips are at even positions and how many are at odd positions, because:
- If we want to move all the chips to an even position, we will only pay the cost for those chips that are currently at odd positions (because moving from odd to even costs 1).
- If we want to move all the chips to an odd position, we will only pay the cost for those chips that are currently at even positions (because moving from even to odd costs 1).
Now that we know moving between even and odd positions costs 1, and moving within the same parity (even to even or odd to odd) is free, the solution becomes straightforward:
- If there are fewer chips at even positions than at odd positions, then it would be cheaper to move all chips to an even position, because fewer chips need to be moved (and each move costs 1).
- Conversely, if there are fewer chips at odd positions, then it would be cheaper to move all chips to an odd position.
So, the approach is to count how many chips are at even positions and how many are at odd positions. Then, the minimum of these two counts will give us the minimum cost to move all the chips to one position. You just move the chips from the side with the fewer count.
Approach
Step 1: Initialize Variables
- Initialize two variables, even and odd, both set to 0. These variables will keep track of the number of chips at even and odd positions in the position array.
Step 2: Traverse the Positions Array
- Loop through the position array.
- For each chip, check if its position is even or odd using pos % 2 == 0.
- Increment the even counter if the position is even, or increment the odd counter if the position is odd.
Step 3: Calculate the Minimum Cost
- After completing the loop, you will have the count of chips at even and odd positions.
- The minimum cost to move all chips to the same position is the smaller of the even and odd counts because:
- Moving all chips to an even position will cost 1 for each chip at an odd position.
- Moving all chips to an odd position will cost 1 for each chip at an even position.
Step 4: Return the Minimum Cost
- Return the smaller of the even and odd counts as the result, which represents the minimum cost needed to move all chips to the same position.
Dry Run
Input: position = [2, 2, 2, 3, 3]
Initialization:
- even = 0 (to count chips at even positions)
- odd = 0 (to count chips at odd positions)
Loop Iterations:
Iteration 1 (pos = 2):
- 2 is even, so increment even by 1.
- even = 1, odd = 0
Iteration 2 (pos = 2):
- 2 is even, so increment even by 1.
- even = 2, odd = 0
Iteration 3 (pos = 2):
- 2 is even, so increment even by 1.
- even = 3, odd = 0
Iteration 4 (pos = 3):
- 3 is odd, so increment odd by 1.
- even = 3, odd = 1
Iteration 5 (pos = 3):
- 3 is odd, so increment odd by 1.
- even = 3, odd = 2
Final Computation:
- The cost to move all chips to an even position is equal to the odd count = 2.
- The cost to move all chips to an odd position is equal to the even count = 3.
- The minimum of even and odd counts is 2.
Final Output: 2
Code for All Languages
C++
class Solution {
public:
int minCostToMoveChips(vector<int>& position) {
// Variables to count the number of chips at even and odd positions
int even = 0, odd = 0;
// Iterate through the positions of the chips
for (int i = 0; i < position.size(); i++) {
// If the position is even, increment the even counter
if (position[i] % 2 == 0) {
even++;
} else {
// If the position is odd, increment the odd counter
odd++;
}
}
// The cost is determined by the smaller of the two counts
return min(odd, even);
}
};
Java
class Solution {
public int minCostToMoveChips(int[] position) {
// Variables to count the number of chips at even and odd positions
int even = 0, odd = 0;
// Iterate through the positions of the chips
for (int pos : position) {
if (pos % 2 == 0) {
// Count chips at even positions
even++;
} else {
// Count chips at odd positions
odd++;
}
}
// Return the minimum of odd and even counts
return Math.min(odd, even);
}
}Python
class Solution:
def minCostToMoveChips(self, position: List[int]) -> int:
# Variables to count the number of chips at even and odd positions
even = 0
odd = 0
# Iterate through the positions of the chips
for pos in position:
if pos % 2 == 0:
# Count chips at even positions
even += 1
else:
# Count chips at odd positions
odd += 1
# Return the minimum of odd and even counts
return min(odd, even)
Javascript
var minCostToMoveChips = function(position) {
// Variables to count the number of chips at even and odd positions
let even = 0, odd = 0;
// Iterate through the positions of the chips
for (let pos of position) {
if (pos % 2 === 0) {
// Count chips at even positions
even++;
} else {
// Count chips at odd positions
odd++;
}
}
// Return the minimum of odd and even counts
return Math.min(odd, even);
};Time Complexity : O(n)
Loop Execution: O(n)
We iterate through the position array, which contains n elements.
In each iteration:
- We perform a modulus operation to check if the current position is even or odd, which takes constant time O(1).
- We then increment a counter, which is also a constant-time operation O(1).
Thus, the loop runs n times, and the total time complexity for the loop is O(n).
Final Computation: O(1)
After the loop, we determine the minimum of two variables (the even and odd counters), which is a constant-time operation O(1).
Final Time Complexity: O(n)
The overall time complexity is O(n), where n is the size of the input array.
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space refers to the extra space used by the algorithm aside from the input. In this case, we are using only a few variables: even and odd counters, which require constant space, O(1).
Total Space Complexity: O(n)
The total space includes both the input (the array) and the auxiliary space.
- The input array position takes O(n) space, as it contains n elements.
- The algorithm does not use any additional space proportional to the size of the input, except for the few constant variables.
Thus, the total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a 0-indexed integer array nums and an integer k, perform the following operation exactly k times:
Select and remove an element m to maximize the score, add m + 1 back to the array, and increase the score by m.
A circular typewriter has lowercase English letters 'a' to 'z' with a pointer initially at 'a'.
In each second, you can move the pointer one step clockwise or counterclockwise or type the current character.
Given a string word, return the minimum time in seconds to type the word.