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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Make Array Equalindromic

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array nums having length n. You are allowed to perform a special move any number of times on nums. In one special move, you can choose an index i and a positive integer x, add |nums[i] - x| to the total cost, and change the value of nums[i] to x. An array is considered equalindromic if all the elements are equal to an integer y, where y is a palindromic number less than 10^9. Return an integer denoting the minimum possible total cost to make nums equalindromic by performing any number of special moves.

Key Insights

  • A palindromic number is an integer that reads the same forwards and backwards.
  • The cost to change all elements in the array to a specific palindromic number can be calculated as the sum of absolute differences between the current elements and the target palindromic number.
  • The optimal palindromic number to minimize the total cost is likely to be around the median of the array values, but must also be a palindromic number.
  • Generating palindromic numbers up to a certain limit helps to find the best candidate for the target value.

Space and Time Complexity

Time Complexity: O(n + p), where n is the length of the array and p is the number of palindromic numbers generated up to 10^9.

Space Complexity: O(p), where p is the number of palindromic numbers generated.

Solution

To solve the problem, we can take the following steps:

  1. Generate all palindromic numbers less than 10^9.
  2. For each palindromic number, calculate the total cost to convert all elements of the array to that palindromic number.
  3. Return the minimum cost among all calculated costs.

The approach utilizes a list to store palindromic numbers and iterates through each number to compute the conversion cost efficiently.

Code Solutions

def is_palindrome(num):
    return str(num) == str(num)[::-1]

def generate_palindromes(limit):
    palindromes = []
    for i in range(1, limit):
        if is_palindrome(i):
            palindromes.append(i)
    return palindromes

def min_cost_to_make_equalindromic(nums):
    limit = 10**9
    palindromes = generate_palindromes(limit)
    
    min_cost = float('inf')
    
    for pal in palindromes:
        cost = sum(abs(num - pal) for num in nums)
        min_cost = min(min_cost, cost)
        
    return min_cost

# Example usage
print(min_cost_to_make_equalindromic([1, 2, 3, 4, 5]))  # Output: 6
← Back to All Questions