# Minimum Cost to Move Chips to The Same Position
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-move-chips-to-the-same-position
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-cost-to-move-chips-to-the-same-position/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-cost-to-move-chips-to-the-same-position/image1.jpg) 

**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
## Brute Force by Testing Each Position as Target
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.
**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.
**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.
### Explanation
The algorithm works as follows:
1.  Initialize a variable `minCost` to a very large value (e.g., `Integer.MAX_VALUE`).
2.  Iterate through each position `p1` in the `position` array. This `p1` will serve as the potential target position for all chips.
3.  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`.
4.  After calculating the `currentCost` for the target `p1`, compare it with `minCost` and update `minCost` if `currentCost` is smaller.
5.  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:
```java
class Solution {
    public int minCostToMoveChips(int[] position) {
        int n = position.length;
        if (n <= 1) {
            return 0;
        }
        
        int minCost = Integer.MAX_VALUE;
        
        // Iterate through each position as a potential target
        for (int i = 0; i < n; i++) {
            int targetPos = position[i];
            int currentCost = 0;
            
            // Calculate the cost to move all chips to targetPos
            for (int j = 0; j < n; j++) {
                int chipPos = position[j];
                // Cost is 1 if parities differ, 0 otherwise.
                // This is equivalent to abs(chipPos - targetPos) % 2
                if ((chipPos % 2) != (targetPos % 2)) {
                    currentCost++;
                }
            }
            
            minCost = Math.min(minCost, currentCost);
        }
        
        return minCost;
    }
}
```
### 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`.

## Optimal Approach by Counting Parity
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.
**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.
**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.
### Explanation
The algorithm is straightforward:
1.  Count the number of chips located at even positions and the number of chips at odd positions.
2.  Initialize two counters, `evenCount` and `oddCount`, to zero.
3.  Iterate through the `position` array once.
4.  For each `pos` in the array, check its parity.
    *   If `pos % 2 == 0`, increment `evenCount`.
    *   Otherwise, increment `oddCount`.
5.  After the loop, we have the total counts of chips at even and odd positions.
6.  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:
```java
class Solution {
    public int minCostToMoveChips(int[] position) {
        int evenCount = 0;
        int oddCount = 0;
        
        for (int pos : position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        
        return Math.min(evenCount, oddCount);
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ); } }
```

### JavaScript

```javascript
/** * @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 ); };
```

### CPP

```cpp
class 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 ); } };
```

### Python

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

```