Domain 1EasyCORE

Minimum Cost to Move Chips to The Same Position

We are given an array `position` where each element represents the position of a chip on a number line. The goal is to move all chips to the same position with the minimum cost. Moving a chip by 2 positions (either forward or backward) has no cost, while moving a chip by 1 position incurs a cost of 1. We need to determine the minimum cost required to gather all chips at the same position.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Math#Greedy

1217. Minimum Cost to Move Chips to The Same Position

Model: qwen2.5-coder:14b
Topics: Array,Math,Greedy
FAANG asked: 0
Acceptance rate: 71.0%


Problem Breakdown

We are given an array position where each element represents the position of a chip on a number line. The goal is to move all chips to the same position with the minimum cost. Moving a chip by 2 positions (either forward or backward) has no cost, while moving a chip by 1 position incurs a cost of 1. We need to determine the minimum cost required to gather all chips at the same position.

Inputs:

  • position: An array of integers representing the initial positions of the chips.

Outputs:

  • An integer representing the minimum cost to move all chips to the same position.

Implicit Constraints and Edge Cases:

  • The array can be empty (though the problem states that 1 <= position.length).
  • Positions can be very large (1 <= position[i] <= 10^9).

Intuition

A brute-force approach would involve trying all possible positions to move the chips to, calculating the cost for each scenario, and then choosing the minimum. However, this approach is inefficient due to its high time complexity (O(n^2) or worse).

The key insight is that moving a chip by 2 positions is free, which means we can effectively group chips at even positions together and chips at odd positions together without any cost. The only cost incurred is when moving chips from one group to the other. Therefore, the minimum cost will be the smaller count between the number of chips at even positions and the number of chips at odd positions.

Approach

  1. Count Chips by Position Parity:

    • Initialize two counters: even_count and odd_count.
    • Iterate through the position array.
    • For each position, check if it is even or odd.
    • Increment even_count if the position is even; otherwise, increment odd_count.
  2. Calculate Minimum Cost:

    • The minimum cost to move all chips to the same position will be the smaller of even_count and odd_count.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the position array. We iterate through the array once to count the chips at even and odd positions.
  • Space Complexity: O(1). We use a constant amount of extra space for the counters.

Solution

def minCostToMoveChips(position):
    even_count = 0
    odd_count = 0
    
    for pos in position:
        if pos % 2 == 0:
            even_count += 1
        else:
            odd_count += 1
    
    return min(even_count, odd_count)

Edge Cases Handled

  • Single Chip: If there is only one chip, the cost will be 0 since no movement is needed.
  • All Chips at Same Position: If all chips are already at the same position, the cost will be 0.
  • Mixed Even and Odd Positions: The solution correctly calculates the minimum cost by comparing the counts of even and odd positions.