Problem Description

You have an array nums of integers (0-indexed) with length n. You can perform a special move on this array any number of times (including zero times).

A special move consists of:

1. Choose an index i in the range [0, n - 1] and a positive integer x
2. Add |nums[i] - x| to the total cost
3. Change the value of nums[i] to x

A palindromic number is a positive integer that reads the same forwards and backwards. For example:

• Palindromic: 121, 2552, 65756
• Not palindromic: 24, 46, 235

An array is called equalindromic if all its elements are equal to the same integer y, where y is a palindromic number less than 10^9.

Your task is to find the minimum total cost to transform nums into an equalindromic array by performing any number of special moves.

In other words, you need to:

1. Choose a palindromic number y (less than 10^9)
2. Change all elements in nums to equal y
3. Minimize the sum of |nums[i] - y| for all indices i

The problem essentially asks you to find the optimal palindromic number to which all array elements should be changed, such that the total cost (sum of absolute differences) is minimized.

Intuition

The key insight is that to minimize the total cost of changing all elements to a single value, we should choose a value close to the median of the array. This is a well-known property: the sum of absolute differences Σ|nums[i] - y| is minimized when y is the median of the array.

However, we have an additional constraint - the target value must be a palindromic number. So we can't just use the median directly; we need to find the palindromic number that's closest to the median.

Since there are infinitely many palindromic numbers up to 10^9, we need an efficient way to generate and search through them. The clever observation is that palindromic numbers have a special structure - they're symmetric. We can generate all palindromes by:

1. Taking a number like 123
2. Creating even-length palindrome: 123 → 123321 (append reverse)
3. Creating odd-length palindrome: 123 → 12321 (append reverse without last digit)

Since palindromes up to 10^9 have at most 9 digits, we only need to enumerate numbers up to 10^5 (roughly half the digits) to generate all possible palindromes.

The solution strategy becomes:

1. Pre-generate all palindromic numbers less than 10^9 and sort them
2. Find the median of the input array nums
3. Use binary search to find palindromic numbers near the median
4. Check a small window of palindromes around the median (typically the closest 2-3 palindromes)
5. Calculate the cost for each candidate and return the minimum

The reason we check multiple palindromes near the median (not just the closest one) is that the discrete nature of palindromes means the optimal choice might be slightly off from the theoretical continuous median.

Learn more about Greedy, Math, Binary Search and Sorting patterns.

Solution Approach

The solution consists of two main parts: preprocessing palindromes and finding the minimum cost.

Step 1: Generate All Palindromes

We generate all palindromic numbers less than 10^9 by iterating through numbers from 1 to 10^5:

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]  # Full reverse for even-length palindrome
    t2 = s[:-1][::-1]  # Reverse without last digit for odd-length palindrome
    ps.append(int(s + t1))  # Even-length: 123 → 123321
    ps.append(int(s + t2))  # Odd-length: 123 → 12321
ps.sort()

This generates approximately 2 × 10^5 palindromes. We sort them to enable binary search later.

Step 2: Find the Optimal Palindrome

First, we define a cost function that calculates the total cost to change all elements to a given value x:

def f(x: int) -> int:
    return sum(abs(v - x) for v in nums)

Next, we find the median of the sorted array:

nums.sort()
median_index = len(nums) // 2
median_value = nums[median_index]

Using binary search (bisect_left), we find the position where the median would fit in the palindrome array:

i = bisect_left(ps, nums[len(nums) // 2])

Step 3: Check Candidates Around the Median

Since the optimal palindrome should be close to the median, we check palindromes in a small window around position i:

return min(f(ps[j]) for j in range(i - 1, i + 2) if 0 <= j < len(ps))

This checks three positions:

• ps[i-1]: The palindrome just before the median
• ps[i]: The palindrome at or just after the median
• ps[i+1]: The next palindrome after that

The boundary check 0 <= j < len(ps) ensures we don't go out of bounds.

Time Complexity: O(n log n) for sorting nums, plus O(n) for each cost calculation (done a constant number of times).

Space Complexity: O(M) where M ≈ 2 × 10^5 is the number of palindromes stored.

Example Walkthrough

Let's walk through a small example with nums = [1, 25, 99, 4].

Step 1: Generate palindromes First, we generate palindromic numbers. For illustration, let's show a few relevant ones:

• From 1: creates 11 (even) and 1 (odd)
• From 2: creates 22 (even) and 2 (odd)
• From 3: creates 33 (even) and 3 (odd)
• ...continuing this pattern...
• From 10: creates 1001 (even) and 101 (odd)
• From 11: creates 1111 (even) and 111 (odd)

After generating all palindromes up to 10^9 and sorting them, we get: ps = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, ...]

Step 2: Find the median of nums Sort nums: [1, 4, 25, 99] The median index is len(nums) // 2 = 2, so the median value is nums[2] = 25.

Step 3: Binary search for palindromes near median Using binary search on our palindrome array ps, we find where 25 would fit:

• 25 would be inserted between 22 and 33
• bisect_left(ps, 25) returns index 11 (pointing to 33)

Step 4: Check candidate palindromes We check palindromes at indices [10, 11, 12] which correspond to values [22, 33, 44]:

For palindrome 22:

• Cost = |1-22| + |4-22| + |25-22| + |99-22|
• Cost = 21 + 18 + 3 + 77 = 119

For palindrome 33:

• Cost = |1-33| + |4-33| + |25-33| + |99-33|
• Cost = 32 + 29 + 8 + 66 = 135

For palindrome 44:

• Cost = |1-44| + |4-44| + |25-44| + |99-44|
• Cost = 43 + 40 + 19 + 55 = 157

Step 5: Return minimum cost The minimum cost is 119, achieved by changing all elements to palindrome 22.

This example demonstrates why we check multiple palindromes around the median - even though 33 is closer to the median value of 25, the palindrome 22 actually gives us a lower total cost due to the distribution of values in the array.

Solution Implementation

Time and Space Complexity

Time Complexity:

The code consists of two main parts: preprocessing palindromes and solving the main problem.

1. Preprocessing palindromes:

   • The loop runs from 1 to 10^5, creating O(10^5) iterations
   • For each number i, string operations like str(i), s[::-1], and s[:-1][::-1] take O(log i) time (proportional to number of digits)
   • Converting back to integer takes O(log i) time
   • Total preprocessing: O(10^5 * log(10^5)) = O(10^5 * 5) = O(10^5)
   • Sorting the palindromes list: O(|ps| * log|ps|) where |ps| = 2 * 10^5, so O(2 * 10^5 * log(2 * 10^5)) = O(10^5 * log(10^5))

2. Main solution:

   • Sorting nums: O(n * log n) where n is the length of input array
   • Binary search using bisect_left: O(log|ps|) = O(log(2 * 10^5)) = O(log(10^5))
   • Computing minimum cost: evaluates function f at most 3 times, each taking O(n) time
   • Total for main solution: O(n * log n + n) = O(n * log n)

Overall Time Complexity: O(10^5 * log(10^5) + n * log n) where the preprocessing is done once and can be amortized if multiple test cases exist.

Space Complexity:

1. Palindrome storage: The list ps stores 2 * 10^5 palindrome numbers, each requiring O(1) space, totaling O(10^5)

2. Input storage: The sorted nums array takes O(n) space (in-place sorting or copy depending on implementation)

3. Temporary variables: String operations create temporary strings of length O(log(10^5)) = O(5), which is O(1)

Overall Space Complexity: O(10^5 + n) where n is the length of the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Palindrome Generation Logic

A common mistake is reversing the string incorrectly when creating palindromes. For example:

• Wrong: Using num_str + num_str[:-1][::-1] for odd-length palindromes (this creates even-length)
• Wrong: Using num_str + num_str[::-1] for even-length palindromes (this creates odd-length)

Solution: Remember that odd-length palindromes have a single center digit, while even-length palindromes mirror completely:

# Correct generation
even_length = num_str + num_str[::-1]      # 123 → 123321 (6 digits)
odd_length = num_str + num_str[:-1][::-1]  # 123 → 12321 (5 digits)

2. Missing Edge Cases in Palindrome Generation

The code generates palindromes starting from 1, but misses single-digit palindromes (1-9) when using the standard generation method since they would be duplicated.

Solution: The current approach actually handles this correctly by starting from 1, which generates all necessary palindromes including single digits through the odd-length formula.

3. Insufficient Window Size for Checking Candidates

Checking only [i-1, i+1] (3 positions) might miss the optimal palindrome, especially when there are large gaps between consecutive palindromes or when the array has outliers.

Solution: Expand the search window slightly to be more robust:

# Check a wider range of candidates
window_size = 5  # or more depending on requirements
min_cost = float('inf')
for j in range(max(0, closest_index - window_size), 
               min(len(palindromes), closest_index + window_size + 1)):
    min_cost = min(min_cost, calculate_total_difference(palindromes[j]))

4. Integer Overflow for Large Palindromes

When generating palindromes up to 10^9, concatenating strings like "99999" + "99999" would create 9999999999 which exceeds 10^9.

Solution: Filter out palindromes that exceed the limit:

palindromes = []
for i in range(1, 10**5 + 1):
    num_str = str(i)
    even_pal = int(num_str + num_str[::-1])
    odd_pal = int(num_str + num_str[:-1][::-1])
  
    if even_pal < 10**9:
        palindromes.append(even_pal)
    if odd_pal < 10**9:
        palindromes.append(odd_pal)

5. Using Mean Instead of Median

Using the mean (average) as the reference point instead of the median can lead to suboptimal results when the array has outliers.

Solution: Always use the median for minimizing sum of absolute differences:

nums.sort()
median = nums[len(nums) // 2]  # Correct: use median
# NOT: mean = sum(nums) // len(nums)  # Wrong for this problem

6. Not Handling Empty Array or Single Element

The code doesn't explicitly handle edge cases like empty arrays or single-element arrays.

Solution: Add validation at the beginning:

def minimumCost(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        # Find closest palindrome to the single element
        idx = bisect_left(palindromes, nums[0])
        candidates = []
        if idx > 0:
            candidates.append(palindromes[idx - 1])
        if idx < len(palindromes):
            candidates.append(palindromes[idx])
        return min(abs(nums[0] - p) for p in candidates)