Skip to main content
Talentd

Minimum Cost to Move Chips to The Same Position - Solution & Explanation

EasyArrayMathGreedy14 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You get an array where position[i] represents the location of the i-th chip. Moving a chip by 2 positions costs 0, while moving it by 1 position costs 1. The task is to move all chips to the same position with the minimum total cost.

Approach 1: Counting Even and Odd Positions (O(n) time, O(1) space)

The key observation comes from movement cost. Moving a chip by 2 steps costs nothing, which means you can freely move between positions with the same parity (even → even or odd → odd). Cost only appears when switching parity. Iterate through the array once and count how many chips are on even positions and how many are on odd positions. If you move all chips to an even position, every chip currently on an odd position costs 1 to move. If you move everything to an odd position, every chip on an even position costs 1. The minimum cost is simply min(evenCount, oddCount). This greedy counting strategy works because all same-parity moves are free, so the only cost is flipping parity.

This approach uses simple iteration over the array and a greedy decision based on which parity group is smaller.

Approach 2: Use Modular Arithmetic (O(n) time, O(1) space)

The same idea can be expressed more mathematically using position[i] % 2. The modulo operation directly tells whether a position is even or odd. Iterate through the array and increment counters depending on the result of the modulo operation. Since moving by 2 preserves parity, all chips with the same modulo value can gather at one position for free. Chips with the opposite modulo require a single move costing 1. After processing the array, return the minimum of the two counts.

This formulation emphasizes the mathematical insight behind the problem and highlights the role of modular arithmetic. It leads to the same optimal greedy decision and requires only constant extra space.

Recommended for interviews: Interviewers expect the parity observation that moving by 2 is free. The optimal solution counts chips on even and odd positions and returns the smaller group size. Brute force simulations are unnecessary here. Demonstrating the parity insight quickly shows strong problem-solving and pattern recognition.

Approach 1: Counting Even and Odd Indices

The main observation here is that moving chips from position p to p+2 or p-2 incurs no cost. Hence, the cost to align all chips into one position is essentially the cost of moving all odd-indexed chips to even positions or vice versa.

To achieve this, count the number of chips at odd positions and the number of chips at even positions. The minimum cost to move all chips to the same position is the lesser of the two counts.

This C solution iterates through each chip position and counts how many are at odd and even positions. The minimum of these two counts determines the cost to align all chips.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 2: Use Modular Arithmetic

A similar but slightly varied approach leverages modular arithmetic to classify indices. As the cost is incurred when moving by an odd number of steps, the strategy remains to count parity of indices and work from there.

By using an array `count` to track counts of even and odd indices, this solution provides an efficient way to determine the minimum movement cost using basic arithmetic for index parity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for iterating through the list of positions.
Space Complexity: O(1), with fixed space used to track counts.

Try this approach in the editor →

Approach 3: Quick Thinking

Move all chips at even indices to position 0, and all chips at odd indices to position 1, all at a cost of 0. Then, choose the position (either 0 or 1) with fewer chips and move these chips to the other position. The minimum cost required is the smaller quantity of chips.

The time complexity is O(n), and the space complexity is O(1). Here, n is the number of chips.

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Even and Odd Indices

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

Use Modular Arithmetic

Time Complexity: O(n) for iterating through the list of positions.
Space Complexity: O(1), with fixed space used to track counts.

Quick Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting Even and Odd PositionsO(n)O(1)Best general solution. Single pass with simple counters.
Modular Arithmetic (Parity Check)O(n)O(1)When expressing the parity logic using mathematical reasoning.

Video Solution

Minimum Cost to Move Chips to The Same Position | LeetCode 1217 | C++, Java, Python • Knowledge Center • 6,808 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Move Chips to The Same Position easy or hard?
Minimum Cost to Move Chips to The Same Position is classified as an Easy problem. The challenge is recognizing that moves by 2 are free, which groups positions by parity and reduces the solution to a simple counting strategy.
Minimum Cost to Move Chips to The Same Position Python/Java solution
The implementation in Python or Java iterates through the array and checks position % 2 to classify each chip as even or odd. Maintain two counters and return the minimum of the two. The algorithm runs in O(n) time and uses O(1) extra space.
How to solve Minimum Cost to Move Chips to The Same Position in O(n)?
Iterate through the array and check the parity of each position using position[i] % 2. Count how many chips are on even positions and how many are on odd positions. Since moves of 2 are free, chips within the same parity group can merge without cost. The final answer is min(evenCount, oddCount).
What is the best approach for Minimum Cost to Move Chips to The Same Position?
The optimal approach counts how many chips are on even positions and how many are on odd positions. Moving a chip by 2 costs 0, so chips can move freely between positions with the same parity. Only moves between even and odd positions cost 1. The minimum cost is the smaller of the two counts.
Is Minimum Cost to Move Chips to The Same Position asked at Google/Amazon/Meta?
Greedy parity-based problems like this appear frequently in coding interviews at companies such as Amazon, Google, and Meta. While the exact question may vary, recognizing patterns like parity grouping and zero-cost moves is a common interview skill.
What data structure is used in Minimum Cost to Move Chips to The Same Position?
The problem primarily uses an array for input and simple integer counters to track parity groups. No advanced data structures are required because the greedy insight reduces the task to counting.
What is the time complexity of Minimum Cost to Move Chips to The Same Position?
The optimal solution runs in O(n) time because it scans the array once to count chips at even and odd indices. Space complexity is O(1) since only two counters are maintained regardless of input size.

Ready to solve this problem?

Practice Minimum Cost to Move Chips to The Same Position with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Operations to Move All Balls to Each Box

Next

Split With Minimum Sum