Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3

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

Example 3:

1
2

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

Solution

Method 1 – Parity Counting

Intuition

The cost to move a chip depends on whether it moves between even and odd positions. Moving by 2 (even steps) is free, so all chips on even positions can be grouped together at zero cost, and similarly for odd positions. The only cost is moving chips between even and odd positions, which costs 1 per chip. Thus, the minimum cost is moving the smaller group (even or odd) to the other.

Approach

  1. Initialize counters for chips at even and odd positions.
  2. Iterate through the positions:
    • If the position is even, increment the even counter.
    • If the position is odd, increment the odd counter.
  3. The answer is the minimum of the two counters, as that’s the minimum number of chips that need to cross parity (incurring cost).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
	 int minCostToMoveChips(vector<int>& pos) {
		  int even = 0, odd = 0;
		  for (int p : pos) {
				if (p % 2 == 0) even++;
				else odd++;
		  }
		  return min(even, odd);
	 }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func minCostToMoveChips(pos []int) int {
	 even, odd := 0, 0
	 for _, p := range pos {
		  if p%2 == 0 {
				even++
		  } else {
				odd++
		  }
	 }
	 if even < odd {
		  return even
	 }
	 return odd
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	 public int minCostToMoveChips(int[] pos) {
		  int even = 0, odd = 0;
		  for (int p : pos) {
				if (p % 2 == 0) even++;
				else odd++;
		  }
		  return Math.min(even, odd);
	 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
	 fun minCostToMoveChips(pos: IntArray): Int {
		  var even = 0
		  var odd = 0
		  for (p in pos) {
				if (p % 2 == 0) even++
				else odd++
		  }
		  return minOf(even, odd)
	 }
}
1
2
3
4
5
6
7
8
9

class Solution:
	 def minCostToMoveChips(self, pos: list[int]) -> int:
		  even = odd = 0
		  for p in pos:
				if p % 2 == 0:
					 even += 1
				else:
					 odd += 1
		  return min(even, odd)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
	 pub fn min_cost_to_move_chips(pos: Vec<i32>) -> i32 {
		  let (mut even, mut odd) = (0, 0);
		  for &p in &pos {
				if p % 2 == 0 {
					 even += 1;
				} else {
					 odd += 1;
				}
		  }
		  even.min(odd)
	 }
}

Complexity

  • Time: O(n), where n is the number of chips (positions).
  • Space: O(1), only counters are used.