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 theminimum possible total cost to make _nums equalindromic by performing any number of special moves.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy + Palindrome Enumeration

Intuition

To minimize the cost, for each element in nums, we want to change it to a palindromic number with the least cost. For each index, try all palindromic numbers within a reasonable range and pick the one with the minimum cost. The total cost is the sum of these minimum costs.

Approach

  1. For each number in nums, enumerate palindromic numbers close to it (e.g., within ±10000).
  2. For each palindromic number, calculate the cost to change the current number to it.
  3. For each index, pick the palindromic number with the minimum cost.
  4. Sum up the minimum costs for all indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool isPal(int x) {
        int y = 0, t = x;
        while (t) { y = y * 10 + t % 10; t /= 10; }
        return x == y;
    }
    int minimumCost(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            int best = INT_MAX;
            for (int d = -10000; d <= 10000; ++d) {
                int y = x + d;
                if (y > 0 && isPal(y)) best = min(best, abs(x - y));
            }
            ans += best;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func isPal(x int) bool {
    y, t := 0, x
    for t > 0 {
        y = y*10 + t%10
        t /= 10
    }
    return x == y
}
func minimumCost(nums []int) int {
    ans := 0
    for _, x := range nums {
        best := 1<<31 - 1
        for d := -10000; d <= 10000; d++ {
            y := x + d
            if y > 0 && isPal(y) {
                if abs(x-y) < best { best = abs(x-y) }
            }
        }
        ans += best
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    boolean isPal(int x) {
        int y = 0, t = x;
        while (t > 0) { y = y * 10 + t % 10; t /= 10; }
        return x == y;
    }
    public int minimumCost(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            int best = Integer.MAX_VALUE;
            for (int d = -10000; d <= 10000; ++d) {
                int y = x + d;
                if (y > 0 && isPal(y)) best = Math.min(best, Math.abs(x - y));
            }
            ans += best;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun isPal(x: Int): Boolean {
        var y = 0; var t = x
        while (t > 0) { y = y * 10 + t % 10; t /= 10 }
        return x == y
    }
    fun minimumCost(nums: IntArray): Int {
        var ans = 0
        for (x in nums) {
            var best = Int.MAX_VALUE
            for (d in -10000..10000) {
                val y = x + d
                if (y > 0 && isPal(y)) best = minOf(best, kotlin.math.abs(x - y))
            }
            ans += best
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def is_pal(self, x: int) -> bool:
        return str(x) == str(x)[::-1]
    def minimumCost(self, nums: list[int]) -> int:
        ans = 0
        for x in nums:
            best = float('inf')
            for d in range(-10000, 10001):
                y = x + d
                if y > 0 and self.is_pal(y):
                    best = min(best, abs(x - y))
            ans += best
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn minimum_cost(nums: Vec<i32>) -> i32 {
        fn is_pal(x: i32) -> bool {
            let s = x.to_string();
            s.chars().rev().collect::<String>() == s
        }
        let mut ans = 0;
        for &x in &nums {
            let mut best = i32::MAX;
            for d in -10000..=10000 {
                let y = x + d;
                if y > 0 && is_pal(y) {
                    best = best.min((x-y).abs());
                }
            }
            ans += best;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    isPal(x: number): boolean {
        return x.toString() === x.toString().split('').reverse().join('');
    }
    minimumCost(nums: number[]): number {
        let ans = 0;
        for (const x of nums) {
            let best = Number.MAX_SAFE_INTEGER;
            for (let d = -10000; d <= 10000; ++d) {
                const y = x + d;
                if (y > 0 && this.isPal(y)) best = Math.min(best, Math.abs(x - y));
            }
            ans += best;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * R) where n is the length of nums and R is the range of palindromic numbers checked (here, 20001).
  • 🧺 Space complexity: O(1).