algoadvance

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

Problem Statement

We have n chips, where the position of the i-th chip is position[i]. We need to move all chips to the same position. In one step, we can:

1. Move a chip by 2 units to any position at no cost (i.e., from position x to x + 2 or x - 2).
2. Move a chip by 1 unit to any position for a cost of 1 (i.e., from position x to x + 1 or x - 1).

Given an array position, return the minimum cost needed to move all the chips to the same position.

Clarifying Questions

1. Range of n: How large can n be? Answer: The maximum length of the array position can be up to 100.

2. Range of positions: Are the positions large? Answer: No constraints are specified, so positions can be any integers.

3. Output Expectations: Should the output be the minimum cost as an integer? Answer: Yes, the output should be a single integer representing the minimum cost.

Strategy

1. Observation:
   • Moving chips to an even-indexed position from another even-indexed position or from an odd-indexed position to another odd-indexed position has no cost (free moves).
   • Moving a chip from an odd-indexed position to an even-indexed position or vice-versa incurs a cost of 1 per move.
2. Approach:
   • Count the number of chips in even positions and the number of chips in odd positions.
   • The minimum number of moves required would be moving all chips from the positions with the fewer chips to the positions with the more chips.
3. Implementation:
   • Iterate through the array and count how many chips are on even indices and odd indices.
   • The result will be the minimum of the two counts.

Code

public 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);
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the position array. We are iterating through the array once.
• Space Complexity: O(1), since we are only using a constant amount of additional space to store the counts of even and odd positions.

This approach ensures that we efficiently calculate the minimum cost required to move all chips to the same position.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?