Minimum Cost to Move Chips to The Same Position

Easy
350.

Minimum Cost to Move Chips to The Same Position

Minimum Cost to Move Chips to The Same Position is an easy coding problem on arrays, math and greedy, asked in Amazon, Adobe and Morgan Stanley interviews.

There are chips at various positions; position[i] is where the i-th chip sits. You may move any chip:

  • by 2 in either direction, at cost 0;
  • by 1 in either direction, at cost 1.

Return the minimum total cost of gathering all the chips onto one position.

Example 1

Input
position = [1,2,3]
Output
1
Explanation
Move the chip at 1 to 3 for free, then the chip at 2 to 3 for 1.

Example 2

Input
position = [2,2,2,3,3]
Output
2

Example 3

Input
position = [1,1000000000]
Output
1

Constraints

  • 1 <= position.length <= 40
  • 1 <= position[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} position
 * @return {number}
 */
var minCostToMoveChips = function(position) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Move Chips to The Same Position — Solution

Minimum Cost to Move Chips to The Same Position solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Cost to Move Chips to The Same Position is an easy coding problem on arrays, math and greedy, asked in Amazon, Adobe and Morgan Stanley interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Greedy
  • Asked at: Amazon, Adobe, Morgan Stanley
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are chips at various positions; position[i] is where the i-th chip sits. You may move any chip:

  • by 2 in either direction, at cost 0;
  • by 1 in either direction, at cost 1.

Return the minimum total cost of gathering all the chips onto one position.

Example 1

Input: position = [1,2,3]
Output: 1
Explanation: Move the chip at 1 to 3 for free, then the chip at 2 to 3 for 1.

Example 2

Input: position = [2,2,2,3,3]
Output: 2

Example 3

Input: position = [1,1000000000]
Output: 1

Constraints

  • 1 <= position.length <= 40
  • 1 <= position[i] <= 1000000000

Hints for Minimum Cost to Move Chips to The Same Position

  1. Hint 1

    Moving by 2 is free, so a chip can reach any position of the same parity at no cost.

  2. Hint 2

    Gather every even chip onto one even square and every odd chip onto one odd square — still free.

  3. Hint 3

    Then one group has to step across, costing 1 per chip, so the answer is the size of the smaller group.

How to solve Minimum Cost to Move Chips to The Same Position

Moves of 2 are free, so all even-position chips can gather for free and so can all odd ones; then the smaller group crosses over at 1 per chip.

Approach

  1. Count chips at even positions.
  2. Return min(even, total - even).

Why it works

Parity is the only invariant a free move cannot change; merging the two parity classes costs one unit per chip that changes parity, and moving the smaller class is cheapest.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The actual positions beyond their parity are irrelevant.

Reference solution

Python

def minCostToMoveChips(position) -> int:
    even = sum(1 for p in position if p % 2 == 0)
    return min(even, len(position) - even)

Java

public static int minCostToMoveChips(int[] position) {
    int even = 0, odd = 0;
    for (int p : position) {
        if (p % 2 == 0) even++;
        else odd++;
    }
    return Math.min(even, odd);
}

C++

int minCostToMoveChips(vector<int>& position) {
    int even = 0, odd = 0;
    for (int p : position) {
        if (p % 2 == 0) even++;
        else odd++;
    }
    return min(even, odd);
}

JavaScript

var minCostToMoveChips = function(position) {
    let even = 0, odd = 0;
    for (let i = 0; i < position.length; i++) {
        if (position[i] % 2 === 0) even++;
        else odd++;
    }
    return Math.min(even, odd);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms