Minimum Operations to Make Every Element Palindromic - Solution & Explanation

Medium11 min read

Problem Statement

You are given an integer array nums.

In one operation, you may choose an index i and either increment or decrement nums[i] by 2.

Return the minimum number of operations required to make every element in nums a positive palindrome. Different elements may be changed into different palindromic integers.

Example 1:

Input: nums = [10,12,14,16]

Output: 9

Explanation:

One optimal sequence of operations is:

Decrement nums[0] by 2 once to change it from 10 to 8.
Decrement nums[1] by 2 twice to change it from 12 to 8.
Decrement nums[2] by 2 three times to change it from 14 to 8.
Increment nums[3] by 2 three times to change it from 16 to 22.

After 1 + 2 + 3 + 3 = 9 operations, nums = [8, 8, 8, 22], and every element is a positive palindromic integer.

It can be shown that fewer than 9 operations cannot achieve this.

Example 2:

Input: nums = [9,10,11,10]

Output: 2

Explanation:

Decrement nums[1] and nums[3] by 2 once each.

After 2 operations, nums = [9, 8, 11, 8], and every element is a positive palindromic integer.

At least one operation is needed for each of these two elements, so the minimum number of operations is 2.

Example 3:

Input: nums = [125]

Output: 2

Explanation:

Decrement nums[0] by 2 twice to change it from 125 to 121, which is a positive palindromic integer.

A single operation would change it to 123 or 127, neither of which is palindromic. Thus, the minimum number of operations is 2.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solution

Thinking

Each operation adds or subtracts 2, so parity never changes: nums[i] can only become a positive palindrome of the same parity. The elements are independent, and the answer is the sum of each value's distance to the nearest same-parity palindrome, divided by 2.

With n = 10^5 and values up to 10^9, walking from x by steps of 2 until a palindrome appears is too slow.

Every palindrome is a mirrored prefix. Enumerating prefixes 1 ldots 10^5 and forming both even-length and odd-length palindromes covers everything around 10^9. Split them by parity, sort each list, and binary-search the nearest neighbor for every x.

An operation increments or decrements an element by 2, so its parity is invariant and the target palindrome must have the same parity. The elements are independent: for each x, find the nearest same-parity positive palindrome p and add \lvert x - p \rvert / 2.

During preprocessing, enumerate prefixes i = 1, 2, ldots, 10^5 and let s be the decimal representation of i:

Even-length palindrome: s + reverse(s)
Odd-length palindrome: s + reverse(s[:-1])

Store them in two lists by parity and sort each list. This range covers all palindromes with up to about 12 digits, which is enough for values up to 10^9.

For each x, binary-search the first palindrome that is at least x in the same-parity list, compare it with the previous one, and take the smaller distance divided by 2.

Let M be the number of palindromes (about 2 times 10^5). Preprocessing takes O(M log M) and each query takes O(log M). The overall time complexity is O(M log M + n log M), and the space complexity is O(M).