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.

 

Example 1:

Input: position = [1,2,3]
Output: 1
Explanation: First step: Move the chip at position 3 to position 1 with cost = 0.
Second step: Move the chip at position 2 to position 1 with cost = 1.
Total cost is 1.

Example 2:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at poistion 3 to position 2. Each move has cost = 1. The total cost = 2.

Example 3:

Input: position = [1,1000000000]
Output: 1

 

Constraints:

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

思路：这题最大的难点是读懂题意。对于每一个chip来说，它往左或右移偶数步是没有cost的，奇数步是有一个cost的。所以假设这个chip现在在5的位置，那么往左移在没有cost

的前提下，最多可以移到1的位置。如果chip在8的位置，往左移最多可以移到2的位置。那么假设现在已经移完了，所有偶数的都移到了2，所有奇数的都移到了1. 只剩下了两个选择，

把在2的chip移到1，或者是把在1的chip移到2。也即为我们挑选少的那部分移到另一部分。

time complexity：O(n)  space complexity: O(1) 

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