Abstract / Summary

Given two arrays, find the least moves needed to make them similar by changing elements to match at each 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 61% (20k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting

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 makeSimilar method computes the minimum number of operations required to transform one integer list (nums) into another (target) when the only allowed operation is adding or subtracting 2 from any element. Because adding or subtracting 2 preserves the parity of a number, the algorithm works separately on odd and even elements, aligns them by sorting, and aggregates the half-distance between matched pairs. The final result is halved once more to account for the fact that each operation changes two units of distance.

Key Steps

The method begins by initializing an accumulator for the total operation count.

result = 0

It then iterates over the two possible parity values, 0 for even and 1 for odd.

for parity in (0, 1):

Within each iteration, the code extracts the subset of numbers from nums that share the current parity, sorts them, and stores the result in one. The extraction uses a generator expression combined with a bitwise-and test to check parity.

one = sorted(n for n in nums if (n & 1) == parity)

A parallel extraction and sorting is performed on target, producing the list two.

two = sorted(t for t in target if (t & 1) == parity)

The two sorted parity-matched lists are then zipped together, and for each pair the absolute difference is computed, shifted right by one bit (equivalent to integer division by 2), and summed. This sum represents the number of “half-steps” needed for the current parity group and is added to the running total.

result += sum(abs(a - b) >> 1 for a, b in zip(one, two))

After processing both parity groups, the accumulated total is shifted right once more, halving it to obtain the final count of allowed ±2 operations.

return result >> 1

Edge Cases Handled

When either input list is empty, the generator expressions produce empty sequences, the sorted calls return empty lists, and the zip operation yields no pairs. Consequently, the sum contributes zero and the function correctly returns 0.

If all elements share the same parity, the loop still iterates twice, but for the parity lacking elements the corresponding one and two lists are empty, leading to a zero contribution for that iteration.

The use of abs ensures that the direction of the difference (whether nums element is larger or smaller than the matching target element) does not affect the count, handling cases where elements need to be increased or decreased.

Large integer values are safely processed because the arithmetic operations are performed using Python’s arbitrary-precision integers, and the right-shift operator works correctly for any non-negative integer result of abs(a - b).

Performance Optimizations

The algorithm limits work to the necessary parity groups, avoiding any mixing of odd and even numbers that would never be convertible under the allowed operation. By sorting each parity-specific subset independently, the code reduces the amount of data that each sort must handle, which can be beneficial when one parity dominates the input.

Generator expressions inside the sorted calls avoid the creation of intermediate full-size lists before sorting, yielding elements on-the-fly and thus reducing temporary memory pressure.

Bitwise operations are employed for both parity checking (n & 1) and division by two (>> 1). These operations are faster than their arithmetic counterparts (% 2 and // 2) and avoid the overhead of function calls.

Finally, the aggregation of differences uses a single sum over a generator expression, which iterates once over the zipped pairs without constructing an intermediate list of differences. This streamlines the computation and keeps the runtime overhead minimal.

Imagine two toy boxes filled with blocks that have numbers written on them. Some blocks are even numbers and some are odd numbers. The goal is to make the boxes look exactly the same by changing the numbers on the blocks.

Changing a number by two is like putting a block on a special tray that keeps it either even or odd. Because of this, the even blocks can only ever turn into other even blocks, and the odd blocks can only turn into other odd blocks.

First, the blocks are sorted from smallest to largest to see which ones match up best. All of the even blocks are lined up, and all of the odd blocks are lined up separately.

Next, the difference between each pair of blocks is measured. Since the numbers only change by two, the distance between them is divided by two to see how many turns it takes to make them match. These small steps are added together until every block has a partner that is its identical twin. All the work is added up to find the total number of turns needed to get everything to match perfectly.

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

Time: loglinear
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		C++	Java		Python	TS
	WalkCCC		C++	Java		Python
	leetcode.ca		C++	Java	Go	Python	TS
	Progiez		C++	Java		Python
github	charles-wangkai			Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
wisdompeak	C++

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