DSA SheetEasy
EditorialPractice

GREEDY › PART I

Play with Chips

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 27

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionfree movement separates chips into two groups

Moving a chip by two positions keeps it on either odd positions or even positions, and that move costs nothing. Therefore, all chips currently on odd positions can be gathered at any chosen odd position for free, and all chips currently on even positions can be gathered at any chosen even position for free. The actual distances do not matter once their parity is known.

The final position must be either odd or even. If you choose an odd position, every even chip must change parity, costing one per chip, while every odd chip moves for free. Choosing an even position has the opposite cost. The answer is therefore the smaller of the number of odd-position chips and the number of even-position chips.

Approachcount the cost of each possible parity

  1. Create counters for chips on odd and even positions, because the final cost depends only on these two groups rather than on their exact coordinates.
  2. Visit every value in position once, because each chip contributes exactly one unit to one of the two possible parity costs.
  3. Increment the even counter when value % 2 equals 0 and the odd counter otherwise, because moving by two preserves this classification while moving by one changes it.
  4. Return min(odd, even), because choosing an odd destination costs one for every even chip and choosing an even destination costs one for every odd chip.
  5. Do not search for a particular destination, because any destination with the chosen parity gives the same cost and the position values can be as large as 10^9.

Complexityone pass and two counters

MEASUREBOUNDWHY
TimeO(n)The loop reads each of the n chip positions once, performs constant-time parity work, and never revisits a chip or searches across coordinate values.
SpaceO(1) extraOnly two integer counters are maintained regardless of n. The input array is not extra storage, and the returned integer is required output, so neither is counted.
Here n is the number of chips, equal to position.length.

Annotated solutionC++ · one pass · parity counting

CPPCount both parity groups and pay for the smaller group to change parity.
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int odd = 0;
        int even = 0;

        for (int value : position) {
            if (value % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }

        return min(odd, even);
    }
};

The important placement is the final min call. The odd counter is not the cost of choosing an odd destination; it is the cost of choosing an even destination, because every odd chip would need one paid move. Likewise, even is the cost of choosing an odd destination. Taking the smaller counter evaluates both possible destination parities without constructing either destination.

Common mistakesthe two lines that change the answer

Previous · Assign Cookies