Minimum Cost To Move Chips To The Same Position - Leetcode Solution

Problem statement:

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.

Solution approach:

Let's say we have a total of 'n' chips and the positions of the chips are given in an array 'position'. As per the problem statement, we can move a chip to the left or right by 1 or 2 units. If we move a chip to the left or right by 2 units, there is no cost involved. But if we move a chip to the left or right by 1 unit, there is a cost of 1 unit involved.

To minimize the total cost, we should try to move the chips to the closest even or odd position as these positions are only 1 unit away from each other, hence minimum cost will be involved.

For example, if we have chips at positions 1, 2, 3, 4, 5 then the minimum cost to move all the chips to the same position will be 1. We can move the chips at positions 1, 3, and 5 to position 3, resulting in zero cost. And we can move the chips at positions 2 and 4 to position 3, resulting in a total cost of 1.

Therefore, to calculate the minimum cost, we just need to count the number of chips at even and odd positions, and return the minimum count.

Python code:

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        even_count = 0
        odd_count = 0
        for p in position:
            if p % 2 == 0:
                even_count += 1
            else:
                odd_count += 1
        return min(even_count, odd_count)

Time Complexity: O(n)

Space Complexity: O(1)

Explanation: In the above code, we are iterating through the array 'position' and keeping a count of the number of chips at even and odd positions. Finally, we are returning the minimum of these two counts.

Conclusion:

In this problem, we have learned about the cost involved in moving the chips and how we can minimize the cost by moving the chips to the closest even/odd position. By counting the number of chips at even and odd positions, we can get the minimum cost to move all the chips to the same position.

1