We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Make Array Equalindromic

Number: 3229

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a 0-indexed integer array nums, you can perform a "special move" any number of times. In each move, you choose an index i and a positive integer x, add |nums[i] - x| to the total cost, and update nums[i] to x. An array is considered equalindromic if all of its elements are equal to a palindromic number (a positive integer that remains the same when its digits are reversed) that is less than 10^9. The goal is to determine the minimum possible total cost needed to transform the input array into an equalindromic array.

Key Insights

  • The target transformation requires every element to become some palindromic number y (<10^9).
  • The cost for changing an element from a to y is |a - y|.
  • If there were no restrictions on y (palindromicity), the median minimizes the sum of absolute differences.
  • The median might not be palindromic, so we generate candidate palindromic numbers around the median.
  • Sorting the array to get the median and then checking nearby palindromic numbers can efficiently lead to the optimal solution.

Space and Time Complexity

Time Complexity: O(n log n + P * n) where n is the size of the input array and P is the number of palindromic candidates (kept small by limiting the search around the median).
Space Complexity: O(n) for storing and sorting the array.

Solution

We first sort the array to quickly find the median. Since changing all elements to the median minimizes the sum of absolute differences, we generate candidate palindromic numbers in a small window around the median. For each candidate, we compute the cost of transforming the entire array (by summing |num - candidate| for each element) and select the candidate with the minimal cost.

The solution uses:

  • Sorting (to determine the median).
  • A helper function to check whether a number is palindromic.
  • A candidate generation strategy that considers only a limited range around the median (thus keeping P small).

This approach balances the need to satisfy the palindromic requirement while still relying on the median heuristic for optimal cost.

Code Solutions

# Python implementation with line-by-line comments

def is_palindrome(num):
    # Check if the number is the same when its digits are reversed.
    s = str(num)
    return s == s[::-1]

def generate_palindromes(around, limit=10**9):
    # Generate a list of palindromic numbers in a small window around the given 'around' value.
    palindromes = []
    # Define a window of 1000 units on either side of 'around'
    start = max(1, around - 1000)
    end = min(limit, around + 1000)
    for candidate in range(start, end+1):
        if is_palindrome(candidate):
            palindromes.append(candidate)
    return palindromes

def minimumCost(nums):
    # Sort the array to obtain the median value.
    nums.sort()
    n = len(nums)
    median = nums[n // 2]
    
    # Generate candidate palindromic numbers around the median.
    candidates = generate_palindromes(median)
    
    min_cost = float('inf')
    # For each candidate, compute the transformation cost.
    for candidate in candidates:
        cost = sum(abs(num - candidate) for num in nums)
        min_cost = min(min_cost, cost)
    return min_cost

# Example usage:
print(minimumCost([1,2,3,4,5]))         # Expected output: 6
print(minimumCost([10,12,13,14,15]))     # Expected output: 11
print(minimumCost([22,33,22,33,22]))     # Expected output: 22
← Back to All Questions