2967. Minimum Cost to Make Array Equalindromic

Problem Description

You are provided with an integer array nums with a zero-based index. You can perform a sequence of moves on this array with the goal of transforming nums into an equalindromic array, meaning all elements in the array are the same and equal to a palindromic number less than 10^9.

What counts as a move? Well, you choose an index i within the bounds of your array and a positive integer x. You then add the absolute difference between nums[i] and x to your total cost and consequently change nums[i] to x.

The aim is to find the minimum total cost required to make nums equalindromic through any number of such special moves.

Intuition

To minimize the total cost of converting the given array into an equalindromic one, it makes sense to choose a target palindromic number close to the median of the nums array. Why the median? Because it minimizes the sum of absolute differences for the elements of nums – which is essentially our total cost.

To find the closest palindromic number to the median of nums, we need a list of all palindromic numbers within the range. For efficiency, we'll consider palindromic numbers up to 10^5, extend each with its reversed counterpart making both even and odd length palindromes, and sort this list.

Once we have our sorted list of palindromic numbers ps and the sorted nums, we look for the palindromic number closest to the median of nums using binary search. We calculate the cost for the selected palindromic numbers around the median and choose the one with the minimum total cost.

This approach works because by leveraging the properties of palindromes and the sorted order of nums, we significantly narrow down the candidate pool of palindromic numbers to consider, ensuring an efficient search for the minimal total cost.

Learn more about Greedy, Math and Sorting patterns.

Solution Approach

The solution is based on the idea that to minimize the total cost, we should transform the array nums into an equalindromic array where all elements are equal to a palindromic number that is as close as possible to the median of nums.

Here's how the solution approach is implemented:

First, we generate a list of possible palindromic numbers up to 10^9, but we do not need to generate each one of them. Because the largest integer in Python is 32 bits, we can only generate palindromes up to 10^5 and form the larger ones by mirroring these smaller ones, producing palindromes of both even and odd lengths.
To create palindromic numbers, we use the string representation of numbers from 1 to 10^5, reverse the string and then concatenate it back to the original, with and without the last digit (for even and odd lengths). All formed palindromes are then sorted and stored in the array ps.
The next step revolves around sorting the nums and finding its median, which is the middle element after sorting. This median will be our reference point.
We perform a binary search in the array ps to find the closest palindromic number to this median. The Python function bisect_left from the bisect module helps us to efficiently locate the insertion point of the median in the sorted palindromic list ps.
Instead of just picking the number we find through binary search, we look at that number and its adjacent neighbors in the ps array to calculate the cost, as they are likely to be the closest. We calculate the cost of making nums equal to each of these palindromic numbers, which is the sum of the absolute differences between each element in nums and the palindromic number.
Finally, the minimum of these calculated costs is the answer to the problem. It represents the lowest total cost needed to convert nums into an array where all elements are equal to a single palindromic number.

By leveraging preprocessing to create the palindromic numbers, sorting to find the median and sensible points of comparison, and binary search to locate the optimal palindromic candidate, this approach ensures that we can quickly find the minimum total cost with high efficiency.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the problem description's approach. Consider an integer array nums:

nums = [1, 3, 96, 99, 50, 51]

We want to transform nums into an array where all elements are the same and equal to a palindromic number with the lowest total cost. Following the steps described in the solution approach:

Generate the list of palindromic numbers (ps). We do it by mirroring smaller numbers up to 10^5. For simplicity, let's consider a much smaller range, as the full range is extensive. Let's say we consider up to 100:

Smaller palindromes: [1, 2, ..., 99, 100]
Palindromes with even length: [11, 22, ..., 9999, 100001]
Palindromes with odd length: [1, 11, ..., 999, 10001]

Combining and sorting these, we would have a list like this:

ps = [1, 11, ..., 999, 10001, ..., 9999, 100001]

Sort the given array nums and find its median:

Sorted nums: [1, 3, 50, 51, 96, 99]
Median of nums: (50 + 51) / 2 = 50.5 (Because our array has an even number of elements, we take the average of the two middle elements)

Perform a binary search to find the closest palindromic number to the median of nums. Let's say binary search finds ps[i] = 44 as the closest palindromic number to 50.5 in our example list ps.

Calculate the cost for ps[i - 1], ps[i], and ps[i + 1] as they are likely to be the closest. Let's assume ps[i - 1] = 33, ps[i + 1] = 55. The costs would then look like this:

Cost for ps[i - 1] = 33: |1 - 33| + |3 - 33| + |50 - 33| + |51 - 33| + |96 - 33| + |99 - 33| = 276
Cost for ps[i] = 44: |1 - 44| + |3 - 44| + |50 - 44| + |51 - 44| + |96 - 44| + |99 - 44| = 214
Cost for ps[i + 1] = 55: |1 - 55| + |3 - 55| + |50 - 55| + |51 - 55| + |96 - 55| + |99 - 55| = 174

Pick the minimum cost from the calculated values:

Lowest total cost: min(276, 214, 174) = 174

So, the minimum total cost required to transform nums into an equalindromic array is 174, achieved when all elements are transformed to 55.

Please note this example uses a very simplified version of the list of palindromic numbers (ps) for illustrative purposes. The real solution would encompass a much broader and precise list, following the range mandated in the problem description (palindromic numbers below 10^9).

Solution Implementation

1# Generate a list of palindromic numbers up to 10 digits long
2palindromic_numbers = []
3for i in range(1, 100001):  # iterate from 1 to 100000
4    num_str = str(i)
5  
6    # Create two types of palindromes: one with the same reverse and another omitting the last digit
7    palindrome_full = num_str + num_str[::-1]  # reverse the entire number and append
8    palindrome_partial = num_str + num_str[:-1][::-1]  # reverse the number without the last digit and append
9  
10    # Convert strings back to integers and add to the palindromic_numbers list
11    palindromic_numbers.append(int(palindrome_full))
12    palindromic_numbers.append(int(palindrome_partial))
13
14# Sort the list of palindromic numbers for later binary search
15palindromic_numbers.sort()
16
17
18class Solution:
19    def minimumCost(self, nums: List[int]) -> int:
20        # Define a function to calculate the cost of changing all numbers in nums to a single given number x
21        def calculate_cost(x: int) -> int:
22            return sum(abs(num - x) for num in nums)
23
24        # Sort the given list to prepare for binary search
25        nums.sort()
26      
27        # Find the first palindromic number which is not less than the median of nums using binary search
28        median_index = len(nums) // 2
29        nearest_palindrome_index = bisect_left(palindromic_numbers, nums[median_index])
30      
31        # Calculate the minimum cost using the nearest palindromic numbers found via binary search
32        # We consider 3 close palindromic numbers - one less than, one equal to, and one greater than the nearest palindrome
33        # The returned answer will be the best (minimum) possible by comparing the calculated costs
34        min_cost = min(
35            calculate_cost(palindromic_numbers[j])
36            for j in range(nearest_palindrome_index - 1, nearest_palindrome_index + 2)
37            if 0 <= j < len(palindromic_numbers)
38        )
39      
40        return min_cost
41

1import java.util.Arrays;
2
3public class Solution {
4    // Precomputed palindromes stored in the array.
5    private static final long[] precomputedPalindromes;
6
7    static {
8        precomputedPalindromes = new long[2 * (int) 1e5];
9        for (int i = 1; i <= 1e5; i++) {
10            // Convert the current index to string.
11            String indexStr = Integer.toString(i);
12            // Create palindrome by reversing and appending the index string to itself.
13            String palindrome1 = new StringBuilder(indexStr).reverse().toString();
14            // Create a second palindrome for the case with an even number of digits.
15            String palindrome2 = new StringBuilder(indexStr.substring(0, indexStr.length() - 1)).reverse().toString();
16            // Store the numerical value of the palindromes into the array.
17            precomputedPalindromes[2 * i - 2] = Long.parseLong(indexStr + palindrome1);
18            precomputedPalindromes[2 * i - 1] = Long.parseLong(indexStr + palindrome2);
19        }
20        // Sort the array of precomputed palindromes.
21        Arrays.sort(precomputedPalindromes);
22    }
23
24    // The array of numbers to be processed.
25    private int[] numbers;
26
27    // The method evaluates the minimum cost to convert all the numbers into a palindrome.
28    public long minimumCost(int[] nums) {
29        this.numbers = nums;
30        // Sort the array of numbers.
31        Arrays.sort(nums);
32        // Locate the position in the array of palindromes that is closest to the median of 'nums'.
33        int index = Arrays.binarySearch(precomputedPalindromes, nums[nums.length / 2]);
34        // If the number is not found, '(-insertion point - 1)' is returned.
35        index = index < 0 ? -index - 1 : index;
36        // Initialize answer with a large value.
37        long answer = 1L << 60;
38        // Check palindromes around the found index for minimum cost.
39        for (int j = index - 1; j <= index + 1; j++) {
40            if (0 <= j && j < precomputedPalindromes.length) {
41                answer = Math.min(answer, calculateCost(precomputedPalindromes[j]));
42            }
43        }
44        return answer;
45    }
46
47    // Helper method to calculate the cost to convert all numbers into a specific palindrome.
48    private long calculateCost(long palindrome) {
49        long cost = 0;
50        for (int num : numbers) {
51            cost += Math.abs(num - palindrome);
52        }
53        return cost;
54    }
55}
56

1#include <algorithm>
2#include <vector>
3#include <string>
4#include <climits>  // For using LLONG_MAX
5
6// Define "long long" as "ll" for convenience.
7using ll = long long;
8
9// Pre-calculated array to store palindrome numbers
10ll palindrome_numbers[2 * 100000];
11
12// Lambda function to initialize the array with palindrome numbers
13// that would be used to calculate minimum cost later on.
14int init = [] {
15    for (int i = 1; i <= 100000; i++) {
16        // Convert the current number into a string
17        string s = to_string(i);
18        // Create a palindrome by appending the reversed string
19        string reversed_full = s;
20        reverse(reversed_full.begin(), reversed_full.end());
21        // Create another palindrome by omitting the last character
22        string reversed_partial = s.substr(0, s.length() - 1);
23        reverse(reversed_partial.begin(), reversed_partial.end());
24        // Store both full and partial palindrome numbers into the array
25        palindrome_numbers[2 * i - 2] = stoll(s + reversed_full);
26        palindrome_numbers[2 * i - 1] = stoll(s + reversed_partial);
27    }
28    // Sort the array for binary search operations
29    sort(palindrome_numbers, palindrome_numbers + 2 * 100000);
30    return 0;  // Must return a value as we're in a lambda
31}();
32
33// Define the Solution class with the method minimumCost
34class Solution {
35public:
36    long long minimumCost(std::vector<int>& nums) {
37        // Sort the input vector to allow binary search and easy access to the median
38        sort(nums.begin(), nums.end());
39        // Find the closest palindrome number to the median of the input vector
40        int median_index = (nums.size() / 2);
41        int palindrome_index = lower_bound(palindrome_numbers, palindrome_numbers + 2 * 100000, nums[median_index]) - palindrome_numbers;
42        // Define a lambda function to calculate the cost of adjusting all numbers in the vector to a given palindrome number
43        auto calculate_cost = [&](ll target) {
44            ll total_cost = 0;
45            for (int value : nums) {
46                total_cost += abs(value - target);
47            }
48            return total_cost;
49        };
50        // Initialize the answer with the maximum possible value of a long long
51        ll minimum_total_cost = LLONG_MAX;
52        // Iterate through the possible palindrome numbers and calculate minimum cost
53        for (int j = palindrome_index - 1; j <= palindrome_index + 1; j++) {
54            if (0 <= j && j < 2 * 100000) {
55                minimum_total_cost = std::min(minimum_total_cost, calculate_cost(palindrome_numbers[j]));
56            }
57        }
58        // Return the minimum cost found
59        return minimum_total_cost;
60    }
61};
62

1// Precomputed array to store palindrome numbers.
2const palindromeNumbers = Array(2e5).fill(0);
3
4// Immediately-invoked function to initialize the palindrome numbers.
5// This function populates the `palindromeNumbers` array with all palindrome numbers generated from 1 to 100000.
6const initialize = (() => {
7    for (let i = 1; i <= 1e5; ++i) {
8        // Convert current number to string
9        const stringNumber: string = i.toString();
10        // Create a palindrome by reversing the string and appending it to the original string
11        const palindrome1: string = stringNumber + stringNumber.split('').reverse().join('');
12        // Create another palindrome by removing the last character, reversing, and appending
13        const palindrome2: string = stringNumber + stringNumber.slice(0, -1).split('').reverse().join('');
14      
15        // Parse the generated strings into numbers and store them
16        palindromeNumbers[2 * i - 2] = parseInt(palindrome1, 10);
17        palindromeNumbers[2 * i - 1] = parseInt(palindrome2, 10);
18    }
19    // Sort the array to make it easy for binary search
20    palindromeNumbers.sort((a, b) => a - b);
21})();
22
23// Function to calculate minimum cost by converting the given array 'nums' 
24// into an array where every number is a palindrome number.
25function minimumCost(nums: number[]): number {
26    // Binary search to find the index of the smallest palindrome
27    // number that is greater than or equal to 'x'.
28    const binarySearch = (x: number): number => {
29        let [left, right] = [0, palindromeNumbers.length];
30        while (left < right) {
31            const mid = left + ((right - left) >> 1);
32            if (palindromeNumbers[mid] >= x) {
33                right = mid;
34            } else {
35                left = mid + 1;
36            }
37        }
38        return left;
39    };
40
41    // Helper function to calculate the cost of converting 'nums'
42    // to a fixed palindrome number 'x'.
43    const calculateCost = (x: number): number => {
44        return nums.reduce((accumulator, currentValue) => accumulator + Math.abs(currentValue - x), 0);
45    };
46
47    // Sort the input array to prepare for median-based optimization.
48    nums.sort((a, b) => a - b);
49    // Binary search to find the closest palindrome number to
50    // the median of 'nums' array, which minimizes the total cost.
51    const medianIndex: number = binarySearch(nums[Math.floor(nums.length/2)]);
52    let minCost: number = Number.MAX_SAFE_INTEGER;
53
54    // Test palindrome numbers around the found median index.
55    for (let j = medianIndex - 1; j <= medianIndex + 1; j++) {
56        if (j >= 0 && j < palindromeNumbers.length) {
57            minCost = Math.min(minCost, calculateCost(palindromeNumbers[j]));
58        }
59    }
60    return minCost;
61}
62

Time and Space Complexity

The time complexity of the code primarily comes from three operations:

Generating the ps list contains all palindromes of up to 5 digits. This involves a loop from 1 to 10**5 and several string operations within the loop. The string operations are constant time since the length of the numbers is bounded by a small constant (the number of digits in 10**5). Thus, this loop is O(10**5).
Sorting the ps list: Once the palindromes are generated, they are sorted. The sort operation has a complexity of O(M \log M), where M is the number of palindrome numbers generated.
The method minimumCost involves sorting the nums list, which is O(n \log n). The binary search bisect_left is O(\log M). The local function f(x) is O(n) for each call as it computes the absolute difference for each element with x, and it is called at most three times due to the range considered in min(f(ps[j]) for j in range(i - 1, i + 2) if 0 <= j < len(ps)). Thus, this part is bounded by O(3n) which simplifies to O(n).

So the overall time complexity is the sum of these – O(10**5) + O(M \log M) + O(n \log n) + O(\log M) + O(n). Since O(M \log M) is the dominant term, the total time complexity simplifies to O(n \log n) due to the assumption that n is in the order of M or larger.

The space complexity comes from storing the palindromes in the ps list, which holds a fixed amount of numbers, 2 * 10**5, leading to O(M) space complexity, where M is the length of the palindrome array.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know