Minimum Cost to Move Chips to The Same Position LeetCode Solution

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 ]