1217. Minimum Cost to Move Chips to The Same Position

Problem

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

• Move the i-th chip by 2 units to the left or to the right with a cost of 0.
• Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

Example 1:

Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Example 2:

Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

Constraints:

• 1 <= chips.length <= 100
• 1 <= chips[i] <= 10^9

Problem Summary

Some chips are placed on a number line, and the position of each chip is stored in the array chips. You can perform either of the following two operations on any chip (any number of times, including 0 times):

• Move the i-th chip 2 units to the left or right, with a cost of 0.
• Move the i-th chip 1 unit to the left or right, with a cost of 1.

Initially, there may also be two or more chips at the same position. Return the minimum cost needed to move all chips to the same position (any position).

Constraints:

• 1 <= chips.length <= 100
• 1 <= chips[i] <= 10^9

Solution Approach

• Given an array, the indices represent coordinate points on the number line, and the elements represent the weights. The movement rules are: moving left or right by 2 units has no cost, while moving left or right by 1 unit costs 1. The question asks for the minimum cost to eventually move all weights onto a single position.
• First, interpret the movement rules: moving from an even position to an even position has no cost, and moving from an odd position to an odd position has no cost. Using this rule, we can stack all weights at no cost onto one odd position and one even position. This way, we only need to care about these two positions. Moreover, these two positions can be adjacent. The final step is to merge these two adjacent stacks of weights together. Since moving left or right by one unit costs 1, the minimum-cost operation is to move the side with fewer weights. If there are fewer weights on odd positions, move those on odd positions; if there are fewer weights on even positions, move those on even positions. Therefore, the solution to this problem becomes extremely simple: traverse the array once, find how many weights are on odd and even positions, and take the smaller count as the final answer.

Code

package leetcode

func minCostToMoveChips(chips []int) int {
	odd, even := 0, 0
	for _, c := range chips {
		if c%2 == 0 {
			even++
		} else {
			odd++
		}
	}
	return min(odd, even)
}