Table of Contents
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 ]