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:
i in the range [0, n - 1], and a positive integer x.|nums[i] - x| to the total cost.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 <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array and can change every element to the same value. The catch: the final value must be a palindromic number. The cost of converting an element is |nums[i] - target|. Your task is to choose a palindromic target that minimizes the total cost.
Approach 1: Brute Force with Palindromic Number List (O(P * n) time, O(P) space)
Generate all palindromic numbers within the valid integer range (up to 1e9). Store them in a list. For each palindrome p, iterate through the array and compute the total cost sum(|nums[i] - p|). Track the minimum cost across all candidates. This works because the valid targets are restricted to palindromes, but the search space can still contain tens of thousands of numbers. The method is straightforward and easy to implement, but it becomes expensive since each palindrome requires a full pass through the array.
This approach relies mostly on sequential iteration over an array. It demonstrates the brute-force baseline clearly and guarantees correctness because every valid palindromic target is tested.
Approach 2: Median + Nearest Palindrome Search (O(n log n + n) time, O(P) space)
The key observation comes from the property of absolute differences: the sum sum(|nums[i] - x|) is minimized when x is the median of the array. Start by sorting the array to find its median using sorting. The optimal target without constraints would be this median. Since the target must be a palindrome, search for the closest palindromic numbers around the median.
Precompute the sorted list of palindromes. Use binary search to find the palindrome closest to the median. Typically, only a few candidates around that position (the nearest lower and higher palindromes) need evaluation. Compute the cost for these candidates and choose the minimum.
This drastically reduces the search space because you no longer evaluate every palindrome. Instead, you leverage the convex nature of the absolute difference function around the median.
Recommended for interviews: The median-based approach with a palindrome search is what interviewers expect. The brute force version proves you understand the constraint that the target must be palindromic. The optimized approach shows deeper insight into how absolute deviation behaves and how to combine that with binary search over candidate palindromes.
This approach involves generating all possible palindromic numbers up to a specified limit and calculating the cost of converting the entire array to each of these palindromic numbers. The minimum cost among all conversions is the desired solution.
The key steps are:
- Generate all potential palindromic numbers up to 109.
- For each palindromic number, calculate the total cost to convert all elements in nums into this number.
- Keep track of the minimal cost encountered during these calculations.
The implemented code generates all possible palindromic numbers below 109 and iterates through each palindromic number to calculate the total cost of converting the entire array to this number. generate_palindromes constructs these numbers by mirroring the digits, both odd and even-length variations, then sorts through this list for any values below 109.
Next, min_cost_to_equalindromic iterates over these generated palindromes, computes the cost for each, and keeps track of the minimum found.
Time Complexity: O(n * k), where n is the number of elements in the input array, and k is the number of palindromic numbers generated and considered.
Space Complexity: O(k), for storing palindromic numbers.
The range of palindrome numbers in the problem is [1, 10^9]. Due to the symmetry of palindrome numbers, we can enumerate in the range of [1, 10^5], then reverse and concatenate them to get all palindrome numbers. Note that if it is an odd-length palindrome number, we need to remove the last digit before reversing. The array of palindrome numbers obtained by preprocessing is denoted as ps. We sort the array ps.
Next, we sort the array nums and take the median x of nums. We only need to find a number in the palindrome array ps that is closest to x through binary search, and then calculate the cost of nums becoming this number to get the answer.
The time complexity is O(n times log n), and the space complexity is O(M). Here, n is the length of the array nums, and M is the length of the palindrome array ps.
Similar problems:
| Approach | Complexity |
|---|---|
| Brute Force with Palindromic Number List | Time Complexity: O(n * k), where n is the number of elements in the input array, and k is the number of palindromic numbers generated and considered. |
| Preprocessing + Sorting + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Palindromic Number List | O(P * n) | O(P) | Good baseline approach when constraints are small or when demonstrating correctness first. |
| Median + Nearest Palindrome Search | O(n log n + n) | O(P) | Preferred solution for large arrays. Uses sorting and evaluates only the closest palindrome candidates. |
2967 Minimum Cost to Make Array Equalindromic || (Median ✅) (why Mean❓ and Range Till 10^4 🙋♂️) • Ayush Rao • 1,693 views views
Watch 6 more video solutions →Practice Minimum Cost to Make Array Equalindromic with our built-in code editor and test cases.
Practice on FleetCode