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

Source: leetcode | Difficulty: EASY
Tags: Data structures

Mathematics

Greedy algorithms

Starter code: class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        

Solutions:
class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		d = {}
		a = 0
		b = 0
		for i in position:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if i % 2 == 0:
				a += d[i]
			else:
				b += d[i]
		return min(a, b)


class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		oddc = evenc = 0
		for i in position:
			if i % 2 == 0:
				evenc += 1
			else:
				oddc += 1
		return oddc if oddc <= evenc else evenc


from collections import Counter

class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		count_e = count_o = 0
		for pos in position:
			if pos % 2 == 0:
				count_e += 1
			else:
				count_o += 1
		return min(count_e, count_o)


class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		position.sort()
		mn = float('inf')

		def getTo(index, p):
			res = 0
			for i in range(len(position)):
				res += abs(p - position[i]) % 2
			return res
		for i in range(len(position)):
			mn = min(mn, getTo(i, position[i]))
		return mn


class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		l = [0, 0]
		for i in range(len(position)):
			if position[i] % 2 == 0:
				l[0] += 1
			else:
				l[1] += 1
		return min(l[0], l[1])


class Solution:

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


class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		record = {}
		for i in range(len(position)):
			if position[i] not in record:
				record[position[i]] = 1
			else:
				record[position[i]] += 1
		max_freq = 0
		odd_freq = 0
		even_freq = 0
		odd_max_freq = 0
		even_max_freq = 0
		odd_rec = 0
		even_rec = 0
		for i in record:
			if i % 2 != 0:
				odd_freq += record[i]
				if record[i] >= odd_max_freq:
					odd_max_freq = record[i]
					odd_rec = i
			else:
				even_freq += record[i]
				if record[i] >= even_max_freq:
					even_max_freq = record[i]
					even_rec = i
		if odd_freq > even_freq:
			rec = odd_rec
		else:
			rec = even_rec
		cost = 0
		for i in position:
			if (rec - i) % 2 == 0 or (i - rec) % 2 == 0:
				continue
			elif rec == i:
				continue
			else:
				cost += 1
		return cost


class Solution:

	def minCostToMoveChips(self, position: List[int]) -> int:
		odd = len([p for p in position if p % 2])
		return min(odd, len(position) - odd)