# Minimum Cost to Move Chips to The Same Position LeetCode Solution

Difficulty Level Easy

## Problem Statement

The Minimum Cost to Move Chips to The Same Position LeetCode Solution – “Minimum Cost to Move Chips to The Same Position” states that you have `n` chips, where the position of the `i`th chip is `position[i]`.

You 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`.

You need to return the minimum cost needed to move all the chips to the same position.

## Example ```Input
[1,2,3]
Output
1```

## Explanation

If we look carefully we can move chips by even places in 0 cost i.e There’s no cost to move numbers by a difference of 2. Hence, we can move all even numbers to 0 and all odd numbers to 1 without any cost.

Now, finally, we need to bring all numbers to zero or 1. Hence, we find out whether moving the odd numbers or the even numbers would incur a greater cost. We return the minimum of the two.

So in the given array, we can find the number of chips at even places (c_even) and the number of chips at odd places (c_odd) and take the minimum of the two.

### WHY Minimum of two?

Since we need to bring all chips at one place so when c_even chips are at 0 and c_odd chips are at 1 then we need to bring either all even chips to 1 or all odd chips to 0 so to make the cost minimum we take the minimum of two so that we need to change the position of the minimum number of chips.

### Optimization

Let’s consider that x chips are found at an even position then the number of chips at the odd position will be: size_of_array – x

So we just need to count the number of even positioned chips.

### Code

```class Solution {
public int minCostToMoveChips(int[] chips) {
int even = 0;
for(int i:chips)
if(i%2==0)
even++;
return Math.min(even,chips.length-even);
}
}```
```class Solution:
def minCostToMoveChips(self, chips: List[int]) -> int:
even = 0
for i in chips:
if(i%2==0):
even+=1
return min(even,len(chips)-even);```
```class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int even=0,odd=0;
for(int i=0;i<chips.size();i++){
if(chips[i]%2==0)
even++;
else
odd++;
}
if(even>odd)
return odd;
return even;

}
};```

## Time & Space Complexity for Minimum Cost to Move Chips to The Same Position LeetCode Solution

Since calculating the number of even/odd chips take a single pass in the array so :

Time Complexity: O(n)
Space Complexity: O(1) [ Since we are only storing two/one variable for any size of input ]

Translate »