Minimum Cost to Move Chips to The Same Position LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple BloombergViews 2618

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 ith 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 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.

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

Example

Minimum Cost to Move Chips to The Same Position LeetCode Solution

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 »