We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Move Chips to The Same Position

Number: 1329

Difficulty: Easy

Paid? No

Companies: Bloomberg, Morgan Stanley

Problem Description

Given an array of chip positions, the task is to move all chips to the same position with minimum cost. Moving a chip by 2 units is free, while moving a chip by 1 unit costs 1. The goal is to minimize the total cost to align all chips.

Key Insights

  • Moving a chip by 2 units does not incur any cost, so chips can be moved freely between positions of the same parity (even or odd).
  • The cost only occurs when moving chips between positions of different parity.
  • The optimal strategy is to move all chips to a position with the parity that already has the most chips, incurring the cost on the fewer chips from the opposite parity.

Space and Time Complexity

Time Complexity: O(n), where n is the number of chips. Space Complexity: O(1), since only a constant amount of extra space is used.

Solution

Since moving chips by 2 units is free, you can bring all chips to any position that shares their parity without cost. Therefore, the problem reduces to deciding whether to move all chips to an even position or an odd position. The total cost is equal to the number of chips in the smaller group (either odd or even) because each chip in the minority group will require a single move costing 1 to switch parity. Thus, the solution is to count the chips in even and odd positions and return the minimum count.

Code Solutions

# Function to determine the minimum cost to move chips to the same position
def minCostToMoveChips(position):
    # Count the number of chips located at even positions
    even_count = sum(1 for pos in position if pos % 2 == 0)
    # The number of chips in odd positions is the total minus the even ones
    odd_count = len(position) - even_count
    # Return the minimum count as those chips will be moved with cost = 1 each
    return min(even_count, odd_count)

# Example usage:
print(minCostToMoveChips([1, 2, 3]))  # Output: 1
← Back to All Questions