{x}
blog image

Minimum Cost to Move Chips to The Same Position

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 position  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

Minimum Cost to Move Chips to The Same Position

This problem asks for the minimum cost to move all chips to the same position. The cost of moving a chip is 0 if the move is by 2 positions and 1 if the move is by 1 position.

Approach

The key observation is that moving a chip from an even-indexed position to another even-indexed position costs 0, and similarly for odd-indexed positions. Therefore, the minimum cost only depends on whether we choose to move all chips to an even or odd position.

We can count the number of chips at even and odd positions. The minimum cost will be the smaller of these two counts, representing the number of chips that need to be moved one position (cost 1).

Algorithm

  1. Count Even and Odd Positions: Iterate through the position array. Count the number of chips at even positions (evenCount) and the number of chips at odd positions (oddCount).

  2. Determine Minimum Cost: The minimum cost is the minimum of evenCount and oddCount.

Code Implementation (Python)

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

Code Implementation (Other Languages)

The core logic remains the same across different languages. The only differences lie in the syntax and function/method naming conventions.

Java:

class Solution {
    public int minCostToMoveChips(int[] position) {
        int evenCount = 0;
        int oddCount = 0;
        for (int pos : position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        return Math.min(evenCount, oddCount);
    }
}

C++:

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int evenCount = 0;
        int oddCount = 0;
        for (int pos : position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        return min(evenCount, oddCount);
    }
};

JavaScript:

/**
 * @param {number[]} position
 * @return {number}
 */
var minCostToMoveChips = function(position) {
    let evenCount = 0;
    let oddCount = 0;
    for (let pos of position) {
        if (pos % 2 === 0) {
            evenCount++;
        } else {
            oddCount++;
        }
    }
    return Math.min(evenCount, oddCount);
};

Go:

func minCostToMoveChips(position []int) int {
    evenCount := 0
    oddCount := 0
    for _, pos := range position {
        if pos%2 == 0 {
            evenCount++
        } else {
            oddCount++
        }
    }
    if evenCount < oddCount {
        return evenCount
    }
    return oddCount
}

Time and Space Complexity

  • Time Complexity: O(n), where n is the number of chips. We iterate through the array once.
  • Space Complexity: O(1). We only use a constant amount of extra space to store the counts of even and odd positions.