Abstract / Summary

Move all chips to one position with minimum cost by moving only those on the wrong parity position.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 73% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of minimizing the cost to move a collection of chips to a common position on a number line. The core insight leveraged by the algorithm is that moving a chip by two units incurs no cost, while moving it by a single unit costs one. Consequently, the optimal strategy reduces to deciding whether the final gathering point should be an odd or an even coordinate. The function computes the count of chips currently on odd positions and the count on even positions, then returns the smaller of the two counts as the minimal total cost.

Key Steps

The algorithm proceeds through a small number of well-defined stages.

Initialization of Counters

odd = even = 0

Two integer variables are created to keep track of how many chips reside on odd indices (odd) and how many reside on even indices (even). The simultaneous assignment ensures both start at zero.

Classification Loop

for p in position:
    if p & 1:
        even += 1
    else:
        odd  += 1

The loop iterates over each element p in the input list position. The expression p & 1 isolates the least-significant bit, effectively testing whether p is odd. If the test yields a true value, the chip is on an odd coordinate, and the even counter is incremented. Otherwise the chip is on an even coordinate, and the odd counter is incremented. The naming of the counters may appear inverted relative to the condition, but the logic correctly tallies the two groups.

Determination of Minimal Cost

return min(odd, even)

After the loop, the function returns the smaller of the two accumulated counts. This value represents the minimal number of single-step moves required, because moving all chips to the parity (odd or even) that already contains the majority of chips avoids unnecessary single-step moves.

Edge Cases Handled

The implementation gracefully handles several boundary conditions without additional code.

When the input list is empty, the loop body never executes, leaving both counters at zero. The final min call returns zero, which is the correct cost because no chips need to be moved.

If all chips share the same parity, either odd or even will be zero after classification. The min function then returns zero, reflecting that no single-step moves are necessary.

The use of the bitwise & operator works correctly for both positive and negative integers, as the parity of a negative number is determined by its least-significant bit in two’s-complement representation. Thus the algorithm correctly classifies negative positions without special handling.

When the list contains duplicate positions, each occurrence is processed independently, incrementing the appropriate counter each time. The final cost calculation remains accurate because the cost depends solely on the count of chips at each parity, not on distinctness of positions.

Performance Optimizations

The code achieves optimal performance through several implicit choices.

The classification loop runs a single pass over the input list, performing only a constant-time bitwise operation and a simple integer increment per element. This eliminates any need for auxiliary data structures or multiple traversals.

By using the bitwise & operator instead of a modulo operation (p % 2), the parity test avoids division, which can be marginally slower on some architectures.

The final result is obtained with a single call to the built-in min function, which compares two scalar values. No additional sorting, hashing, or dynamic programming structures are introduced, keeping the runtime overhead minimal.

Overall, the algorithm exhibits linear time behavior relative to the number of chips and constant auxiliary space, reflecting a highly efficient solution for the problem at hand.

Imagine you have a bunch of game chips scattered all over a long path painted with numbers. You want to bring all the chips together into one single spot so they can hang out in a pile. The rules of this game are special because moving a chip two spaces away is super easy and costs nothing at all. That means all the chips sitting on odd numbers can jump to any other odd number for free, and all the chips on even numbers can jump to any other even number for free.

Because of this, you only really care about two groups. You count how many chips are on odd numbers and how many chips are on even numbers. After you finish counting, you look at your two piles. To spend the least amount of energy, you pick the smaller group and move all those chips one space over to join the bigger group. That way, every single chip ends up in the same place by only moving one space at the very end. The computer goes through the row of chips one by one, keeps track of those two piles, and finds the smallest group to move.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	C++		Java					TS
	WalkCCC	Python	C++		Java
	leetcode.ca	Python	C++	JS	Java	Go
	Progiez	Python	C++		Java
github	BigEggStudy						C#
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem							Ruby
	fpdjsns		C++
	fsq		C++
	halfrost					Go
	JoshCrozier			JS
	keineahnung2345		C++
	lkwq007	Python
	muhammadfarhankt					Go
	suxrobGM						C#
	trung-hn	Python
	varunu28				Java
	YuriSpiridonov	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
Progiez	C++, Java, Python
BigEggStudy	C#
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality