Minimum Cost to Move Chips to The Same Position

Easy

#1136Time: O(N^2), where N is the number of chips. We have a nested loop, where both loops iterate up to N times.Space: O(1). We only use a few variables to store the costs and loop indices, not dependent on the input size.1 company

Patterns

Math Greedy

Data structures

Array

Companies

Morgan Stanley

Prompt

We have n chips, where the position of the i^th 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 i^th 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 <= 100
1 <= position[i] <= 10^9

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process of moving chips for every possible target position. A key observation is that we don't need to check every integer as a potential target. The optimal target position will have the same parity as one of the groups (even or odd) of the initial chip positions. Therefore, we only need to test the positions where chips are already located.

We can iterate through each chip's initial position and consider it as the final destination for all other chips. For each potential destination, we calculate the total cost required to move every chip to that spot. The minimum of these total costs will be our answer.

Algorithm

Initialize minCost to infinity.
For each position p1 in the input array position:
- Set p1 as the targetPosition.
- Initialize currentCost to 0.
- For each position p2 in the position array:
  - Calculate the cost to move from p2 to targetPosition. The cost is 1 if p2 and targetPosition have different parities, and 0 otherwise.
  - Add this cost to currentCost.
- Update minCost = min(minCost, currentCost).
Return minCost.

Walkthrough

The algorithm works as follows:

Initialize a variable minCost to a very large value (e.g., Integer.MAX_VALUE).
Iterate through each position p1 in the position array. This p1 will serve as the potential target position for all chips.
For each p1, calculate the cost to move all chips to this position.
- Initialize a currentCost to 0.
- Iterate through every other position p2 in the position array.
- The cost to move a chip from p2 to p1 is determined by the parity of the distance between them. A move of 2 units is free, and a move of 1 unit costs 1. This means the cost is abs(p1 - p2) % 2.
- Add this cost to currentCost.
After calculating the currentCost for the target p1, compare it with minCost and update minCost if currentCost is smaller.
After iterating through all positions in the input array as potential targets, minCost will hold the minimum possible cost.

Here is a code snippet demonstrating this approach:

1class Solution {2    public int minCostToMoveChips(int[] position) {3        int n = position.length;4        if (n <= 1) {5            return 0;6        }7        8        int minCost = Integer.MAX_VALUE;9        10        // Iterate through each position as a potential target11        for (int i = 0; i < n; i++) {12            int targetPos = position[i];13            int currentCost = 0;14            15            // Calculate the cost to move all chips to targetPos16            for (int j = 0; j < n; j++) {17                int chipPos = position[j];18                // Cost is 1 if parities differ, 0 otherwise.19                // This is equivalent to abs(chipPos - targetPos) % 220                if ((chipPos % 2) != (targetPos % 2)) {21                    currentCost++;22                }23            }24            25            minCost = Math.min(minCost, currentCost);26        }27        28        return minCost;29    }30}

Complexity

Time

O(N^2), where N is the number of chips. We have a nested loop, where both loops iterate up to N times.

Space

O(1). We only use a few variables to store the costs and loop indices, not dependent on the input size.

Trade-offs

Pros

Simple to understand and implement.
It correctly solves the problem by exploring a sufficient subset of possible target positions.

Cons

Inefficient for large inputs due to the quadratic time complexity.
It performs many redundant calculations since the cost only depends on the parity of the target, not its specific value.

A more insightful analysis of the move costs reveals a much simpler solution. Moving a chip by an even number of steps (e.g., pos -> pos + 2k) has a cost of 0. Moving a chip by an odd number of steps (e.g., pos -> pos + 2k + 1) has a cost of 1. This is because any move of an odd distance can be broken down into one move of distance 1 (cost 1) and some number of moves of distance 2 (cost 0).

This means that moving a chip between two positions of the same parity (even to even, or odd to odd) is always free. The only time a cost is incurred is when moving a chip from an even position to an odd one, or vice-versa. This move always costs exactly 1, regardless of the distance.

Therefore, the problem reduces to deciding whether to move all chips to an even position or an odd position.

If we gather all chips at an even position, the cost will be the number of chips initially at odd positions.
If we gather all chips at an odd position, the cost will be the number of chips initially at even positions.

The minimum cost is simply the smaller of these two counts.

Algorithm

Initialize evenCount = 0 and oddCount = 0.
Iterate through each pos in the position array.
If pos is even, increment evenCount.
Else (if pos is odd), increment oddCount.
Return the minimum of evenCount and oddCount.

Walkthrough

The algorithm is straightforward:

Count the number of chips located at even positions and the number of chips at odd positions.
Initialize two counters, evenCount and oddCount, to zero.
Iterate through the position array once.
For each pos in the array, check its parity.
- If pos % 2 == 0, increment evenCount.
- Otherwise, increment oddCount.
After the loop, we have the total counts of chips at even and odd positions.
The minimum cost to move all chips to the same position is min(evenCount, oddCount). This is because we can either move all the oddCount chips to an even position (cost oddCount) or move all the evenCount chips to an odd position (cost evenCount). We choose the cheaper option.

Here is a code snippet for this optimal approach:

1class Solution {2    public int minCostToMoveChips(int[] position) {3        int evenCount = 0;4        int oddCount = 0;5        6        for (int pos : position) {7            if (pos % 2 == 0) {8                evenCount++;9            } else {10                oddCount++;11            }12        }13        14        return Math.min(evenCount, oddCount);15    }16}

Complexity

Time

O(N), where N is the number of chips. We only need to iterate through the input array once.

Space

O(1). We only use two integer variables to store the counts.

Trade-offs

Pros

Extremely efficient with linear time complexity.
Simple and elegant solution based on a key insight about the problem's cost structure.
Optimal solution for this problem.

Cons

Requires a small logical leap to understand why only parity matters, which might not be immediately obvious.

Solutions

Solution

1class Solution { public int minCostToMoveChips ( int [] position ) { int a = 0 ; for ( int p : position ) { a += p % 2 ; } int b = position . length - a ; return Math . min ( a , b ); } }

1/** * @param {number[]} position * @return {number} */ var minCostToMoveChips = function ( position ) { let a = 0 ; for ( let v of position ) { a += v % 2 ; } let b = position . length - a ; return Math . min ( a , b ); };

1class Solution { public: int minCostToMoveChips ( vector < int >& position ) { int a = 0 ; for ( auto & p : position ) a += p & 1 ; int b = position . size () - a ; return min ( a , b ); } };

1class Solution:2    def minCostToMoveChips(self, position: List[int]) -> int: a = sum(p % 2 for p in position) b = len(position) - a return min(a, b)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem