algoadvance

Leetcode 1217. Minimum Cost to Move Chips to The Same Position

Problem Statement

You are given an array position of integers. Here, position[i] represents the position of the i-th chip on a number line. On each move, you can change the position of the i-th chip by either:

Your goal is to find the minimum cost required to move all the chips to the same position.

Clarifying Questions

  1. Are there any constraints on the size of the array position?
    • The usual constraint for LeetCode problems applies, typically up to 10^4 elements.
  2. Is there a specific range for the values in the position array?
    • Values are within the typical integer range on the number line (positive integers).
  3. How should I handle edge cases like an empty array or one with just one element?
    • For an empty array or an array with one element, the cost is 0.

Strategy

The core insight is to recognize that moving chips from even indices to other even indices, or from odd indices to other odd indices, costs 0 (since they can be moved by 2 units). Therefore, the cost only incurs when we move a chip from an even index to an odd index, or vice versa.

  1. Count the number of chips at even positions.
  2. Count the number of chips at odd positions.
  3. The minimum cost to align all chips will be moving the smaller group to the position of the larger group, because moving across groups (even-odd or odd-even) has a cost of 1 per chip.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int minCostToMoveChips(std::vector<int>& position) {
        int evenCount = 0;
        int oddCount = 0;
        
        // Count the number of chips at even and odd positions
        for (int pos : position) {
            if (pos % 2 == 0) {
                ++evenCount;
            } else {
                ++oddCount;
            }
        }
        
        // Return the minimum cost to align all chips
        return std::min(evenCount, oddCount);
    }
};

Time Complexity

The time complexity of this solution is ( O(n) ), where ( n ) is the number of elements in the position array. This is because we iterate over the array once to count the chips at even and odd positions. The space complexity is ( O(1) ) as we only use a few extra variables to store the counts.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI