# Minimum Cost to Make Array Equalindromic
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-to-make-array-equalindromic)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-make-array-equalindromic
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `nums` having length `n`.

You are allowed to perform a special move **any** number of times (**including zero**) on `nums`. In one **special** **move** you perform the following steps **in order**:

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

A **palindromic number** is a positive integer that remains the same when its digits are reversed. For example, `121`, `2552` and `65756` are palindromic numbers whereas `24`, `46`, `235` are not palindromic numbers.

An array is considered **equalindromic** if all the elements in the array are equal to an integer `y`, where `y` is a **palindromic number** less than `109`.

Return _an integer denoting the **minimum** possible total cost to make_ `nums` _**equalindromic** by performing any number of special moves._

**Example 1:**

**Input:** nums = [1,2,3,4,5]
**Output:** 6
**Explanation:** We can make the array equalindromic by changing all elements to 3 which is a palindromic number. The cost of changing the array to [3,3,3,3,3] using 4 special moves is given by |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6.
It can be shown that changing all elements to any palindromic number other than 3 cannot be achieved at a lower cost.

**Example 2:**

**Input:** nums = [10,12,13,14,15]
**Output:** 11
**Explanation:** We can make the array equalindromic by changing all elements to 11 which is a palindromic number. The cost of changing the array to [11,11,11,11,11] using 5 special moves is given by |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11.
It can be shown that changing all elements to any palindromic number other than 11 cannot be achieved at a lower cost.

**Example 3:**

**Input:** nums = [22,33,22,33,22]
**Output:** 22
**Explanation:** We can make the array equalindromic by changing all elements to 22 which is a palindromic number. The cost of changing the array to [22,22,22,22,22] using 2 special moves is given by |33 - 22| + |33 - 22| = 22.
It can be shown that changing all elements to any palindromic number other than 22 cannot be achieved at a lower cost.

**Constraints:**

* `1 <= n <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute-Force with Pre-generated Palindromes
This approach involves generating all possible palindromic numbers up to a certain limit (e.g., slightly above 10^9). Then, for each generated palindrome, we calculate the total cost to make all elements in `nums` equal to this palindrome. We keep track of the minimum cost found across all palindromes.
**Time:** O(K * n), where K is the number of palindromes and n is the length of `nums`. With K ≈ 10^5 and n ≤ 10^5, the complexity is roughly O(10^10), which is not feasible. · **Space:** O(K), where K is the number of palindromes generated. K is approximately 10^5 for palindromes up to 10^9.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to the large number of palindromes to check and the cost calculation for each.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method systematically checks every potential palindromic target value `y`. First, we need a way to get all palindromes. We can generate them by taking a number, converting it to a string, and appending its reverse (with a slight modification for odd/even length palindromes). We would generate all palindromes up to a certain bound (the maximum possible value in `nums` plus some buffer). For each of these palindromes, we iterate through the entire `nums` array, summing up the absolute differences `|nums[i] - y|`. This sum represents the cost for a given palindrome `y`. We maintain a variable to store the minimum cost seen so far and update it whenever a smaller cost is found. While straightforward, this method is computationally expensive because the number of palindromes is large, and for each one, we perform a linear scan of the input array.
### Algorithm
- Generate a list of all palindromic numbers up to a reasonable upper bound (e.g., `10^9 + 10^5`).
- Initialize `minCost` to a very large value (e.g., `Long.MAX_VALUE`).
- Iterate through each palindrome `p` in the generated list.
- For each `p`, calculate the total cost to change all elements of `nums` to `p`. The cost is `currentCost = sum(|num - p| for num in nums)`.
- Update `minCost` with the minimum cost found so far: `minCost = min(minCost, currentCost)`.
- After checking all palindromes, return `minCost`.

## Median-Based Search with Sorting
The core idea is that the cost function `C(y) = sum(|nums[i] - y|)` is minimized when `y` is the median of the array `nums`. Since `y` must be a palindrome, the optimal palindromic value `y` must be one of the two palindromes closest to the median. This approach first finds the median of `nums` by sorting the array. Then, it finds the largest palindrome less than or equal to the median and the smallest palindrome greater than or equal to the median. Finally, it calculates the cost for these two palindromic candidates and returns the minimum of the two.
**Time:** O(n log n + G), where `n` is the number of elements and `G` is the search space for the nearest palindromes. The `O(n log n)` for sorting is the dominant factor. · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used. Java's `Arrays.sort` for primitives has an average space complexity of O(log n).
**Pros:** Significantly more efficient than the brute-force approach.; Correct and guaranteed to pass within the given time constraints.; Relatively easy to implement using standard library functions.
**Cons:** The time complexity is dominated by sorting, which is O(n log n). This can be improved upon.; The linear search for the nearest palindromes can be slow if the median is far from any palindrome, though the gaps between palindromes are not excessively large.
### Explanation
This approach leverages a key mathematical property: the sum of absolute differences to a point is minimized when that point is the median of the data set. Our target value `y` must be a palindrome, so it might not be the exact median. However, because the cost function `C(y)` is convex, the optimal palindromic `y` must be one of the two palindromes that are closest to the true median.

The algorithm proceeds as follows:
1.  Sort the `nums` array to easily find the median. This takes `O(n log n)` time.
2.  The median is `nums[n/2]`.
3.  We then search for the two palindromic candidates that bracket the median. `p1` is found by decrementing from the median, and `p2` is found by incrementing.
4.  We compute the total cost for both `p1` and `p2` and return the smaller one.

```java
import java.util.Arrays;

class Solution {
    public long minimumCost(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long median = (n % 2 == 1) ? nums[n / 2] : (long)(nums[n / 2 - 1] + nums[n / 2]) / 2;

        long p1 = findLowerPalindrome(median);
        long p2 = findUpperPalindrome(median);

        long cost1 = calculateCost(nums, p1);
        long cost2 = calculateCost(nums, p2);

        return Math.min(cost1, cost2);
    }

    private boolean isPalindrome(long n) {
        if (n < 0) return false;
        long original = n;
        long reversed = 0;
        while (n > 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return original == reversed;
    }

    private long findLowerPalindrome(long n) {
        while (!isPalindrome(n)) {
            n--;
        }
        return n;
    }

    private long findUpperPalindrome(long n) {
        while (!isPalindrome(n)) {
            n++;
        }
        return n;
    }

    private long calculateCost(int[] nums, long p) {
        long cost = 0;
        for (int num : nums) {
            cost += Math.abs(num - p);
        }
        return cost;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Determine the median of the array. If `n` is odd, the median `m` is `nums[n/2]`. If `n` is even, the median can be taken as `nums[n/2]` (or any value in the median interval).
- Find the largest palindrome `p1` that is less than or equal to the median `m`. This can be done by starting from `m` and decrementing until a palindrome is found.
- Find the smallest palindrome `p2` that is greater than or equal to the median `m`. This can be done by starting from `m` and incrementing until a palindrome is found.
- Calculate the cost to make all elements equal to `p1`: `cost1 = sum(|nums[i] - p1|)`.
- Calculate the cost to make all elements equal to `p2`: `cost2 = sum(|nums[i] - p2|)`.
- The result is the minimum of `cost1` and `cost2`.

## Optimal Median-Based Search using Quickselect
This approach is an optimization of the previous one. Instead of sorting the entire array to find the median, which takes `O(n log n)` time, we can use a selection algorithm like Quickselect to find the median in `O(n)` average time. Once the median is found, the rest of the logic remains the same: find the two nearest palindromes and calculate the minimum cost.
**Time:** O(n). Finding the median takes O(n), finding palindromes takes O(log m), and calculating costs takes O(n). The total complexity is dominated by the linear scans. · **Space:** O(1) or O(log n), if the selection algorithm is implemented in-place or recursively.
**Pros:** Theoretically optimal time complexity.; Most efficient for very large input arrays.
**Cons:** Implementing a robust, worst-case linear-time selection algorithm (like Median of Medians) is complex.; The practical performance gain over the O(n log n) solution might be small unless `n` is extremely large, as sorting algorithms are highly optimized in standard libraries.
### Explanation
This is the most time-efficient approach. It refines the median-based method by optimizing the step of finding the median. A full sort is overkill when only the median element is required.

1.  **Median Finding**: Use a selection algorithm (e.g., Quickselect) to find the median of `nums` in `O(n)` average time. This avoids the `O(n log n)` cost of sorting.
2.  **Palindrome Finding**: After finding the median `m`, we still need the two closest palindromes. Instead of a simple linear search (incrementing/decrementing), we can directly construct them. We take the first half of the digits of `m`, form a palindrome, and compare it with `m`. Based on the comparison, we might need to adjust the first half (by +1 or -1) to find the other candidate. This finds the palindromes in `O(log m)` time.
3.  **Cost Calculation**: As before, calculate the costs for the two palindrome candidates and return the minimum.

This combination of linear-time median finding and efficient palindrome construction leads to an overall `O(n)` time complexity.

```java
import java.util.Arrays;

class Solution {
    // The main method would use a Quickselect algorithm to find the median in O(n).
    // For brevity, we still use sort here to get the median, but the main idea of this
    // approach is to replace this with a faster selection algorithm.
    public long minimumCost(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long median = (n % 2 == 1) ? nums[n / 2] : (long)(nums[n / 2 - 1] + nums[n / 2]) / 2;

        long p1 = findLowerPalindrome(median);
        long p2 = findUpperPalindrome(median);

        long cost1 = calculateCost(nums, p1);
        long cost2 = calculateCost(nums, p2);

        return Math.min(cost1, cost2);
    }

    // More efficient palindrome finders by construction
    private long findLowerPalindrome(long n) {
        String s = String.valueOf(n);
        int len = s.length();
        String halfStr = s.substring(0, (len + 1) / 2);
        long halfNum = Long.parseLong(halfStr);
        long p = createPalindrome(halfNum);
        if (p > n) {
            p = createPalindrome(halfNum - 1);
        }
        return p;
    }

    private long findUpperPalindrome(long n) {
        String s = String.valueOf(n);
        int len = s.length();
        String halfStr = s.substring(0, (len + 1) / 2);
        long halfNum = Long.parseLong(halfStr);
        long p = createPalindrome(halfNum);
        if (p < n) {
            p = createPalindrome(halfNum + 1);
        }
        return p;
    }

    private long createPalindrome(long half) {
        String s = String.valueOf(half);
        String reversedHalf = new StringBuilder(s).reverse().toString();
        String fullStr = s + reversedHalf.substring(s.length() % 2);
        return Long.parseLong(fullStr);
    }

    private long calculateCost(int[] nums, long p) {
        long cost = 0;
        for (int num : nums) {
            cost += Math.abs(num - p);
        }
        return cost;
    }
}
```
### Algorithm
- Find the median `m` of the `nums` array using a linear-time selection algorithm like Quickselect. This avoids a full sort.
- Once the median `m` is found, identify the two nearest palindrome candidates: `p1` (largest palindrome `<= m`) and `p2` (smallest palindrome `>= m`).
- This search can be optimized by constructing the palindromes from the digits of the median `m` rather than linear searching.
- Calculate the costs for transforming the array to `p1` and `p2`.
- Return the minimum of the two costs.

# Solutions
### Java

```java
public class Solution { private static long [] ps ; private int [] nums ; static { ps = new long [ 2 * ( int ) 1 e5 ]; for ( int i = 1 ; i <= 1 e5 ; i ++) { String s = Integer . toString ( i ); String t1 = new StringBuilder ( s ). reverse (). toString (); String t2 = new StringBuilder ( s . substring ( 0 , s . length () - 1 )). reverse (). toString (); ps [ 2 * i - 2 ] = Long . parseLong ( s + t1 ); ps [ 2 * i - 1 ] = Long . parseLong ( s + t2 ); } Arrays . sort ( ps ); } public long minimumCost ( int [] nums ) { this . nums = nums ; Arrays . sort ( nums ); int i = Arrays . binarySearch ( ps , nums [ nums . length / 2 ]); i = i < 0 ? - i - 1 : i ; long ans = 1L << 60 ; for ( int j = i - 1 ; j <= i + 1 ; j ++) { if ( 0 <= j && j < ps . length ) { ans = Math . min ( ans , f ( ps [ j ])); } } return ans ; } private long f ( long x ) { long ans = 0 ; for ( int v : nums ) { ans += Math . abs ( v - x ); } return ans ; } }
```

### CPP

```cpp
using ll = long long ; ll ps [ 2 * 100000 ]; int init = [] { for ( int i = 1 ; i <= 100000 ; i ++ ) { string s = to_string ( i ); string t1 = s ; reverse ( t1 . begin (), t1 . end ()); string t2 = s . substr ( 0 , s . length () - 1 ); reverse ( t2 . begin (), t2 . end ()); ps [ 2 * i - 2 ] = stoll ( s + t1 ); ps [ 2 * i - 1 ] = stoll ( s + t2 ); } sort ( ps , ps + 2 * 100000 ); return 0 ; }(); class Solution { public: long long minimumCost ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int i = lower_bound ( ps , ps + 2 * 100000 , nums [ nums . size () / 2 ]) - ps ; auto f = [ & ]( ll x ) { ll ans = 0 ; for ( int & v : nums ) { ans += abs ( v - x ); } return ans ; }; ll ans = LLONG_MAX ; for ( int j = i - 1 ; j <= i + 1 ; j ++ ) { if ( 0 <= j && j < 2 * 100000 ) { ans = min ( ans , f ( ps [ j ])); } } return ans ; } };
```

### Python

```python
ps = [] for i in range ( 1 , 10 ** 5 + 1 ): s = str ( i ) t1 = s [:: - 1 ] t2 = s [: - 1 ][:: - 1 ] ps . append ( int ( s + t1 )) ps . append ( int ( s + t2 )) ps . sort () class Solution : def minimumCost ( self , nums : List [ int ]) -> int : def f ( x : int ) -> int : return sum ( abs ( v - x ) for v in nums ) nums . sort () i = bisect_left ( ps , nums [ len ( nums ) // 2 ]) return min ( f ( ps [ j ]) for j in range ( i - 1 , i + 2 ) if 0 <= j < len ( ps ))
```