minimum-cost-to-make-array-equalindromic

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed integer array <code>nums</code> having length <code>n</code>.

You are allowed to perform a special move any number of times (including zero) on <code>nums</code>. In one special move you perform the following steps in order:

<ul>
	<li>Choose an index <code>i</code> in the range <code>[0, n - 1]</code>, and a positive integer <code>x</code>.</li>
	<li>Add <code>|nums[i] - x|</code> to the total cost.</li>
	<li>Change the value of <code>nums[i]</code> to <code>x</code>.</li>
</ul>

A palindromic number is a positive integer that remains the same when its digits are reversed. For example, <code>121</code>, <code>2552</code> and <code>65756</code> are palindromic numbers whereas <code>24</code>, <code>46</code>, <code>235</code> are not palindromic numbers.

An array is considered equalindromic if all the elements in the array are equal to an integer <code>y</code>, where <code>y</code> is a palindromic number less than <code>109</code>.

Return an integer denoting the minimum possible total cost to make <code>nums</code> equalindromic by performing any number of special moves.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

Example 3:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

minimumCost

Minimum Cost to Make Array Equalindromic

Minimum Moves to Equal Array Elements II

minimum-moves-to-equal-array-elements-ii

最小操作次数使数组元素相等 II

Minimum Cost to Make Array Equal

minimum-cost-to-make-array-equal

使数组相等的最小开销

Greedy

Array

Math

Binary Search

Sorting

给你一个长度为 <code>n</code>&nbsp;下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。

你可以对 <code>nums</code>&nbsp;执行特殊操作 任意次&nbsp;（也可以 0&nbsp;次）。每一次特殊操作中，你需要 按顺序&nbsp;执行以下步骤：

<ul>
	<li>从范围&nbsp;<code>[0, n - 1]</code>&nbsp;里选择一个下标 <code>i</code>&nbsp;和一个 正&nbsp;整数&nbsp;<code>x</code>&nbsp;。</li>
	<li>将&nbsp;<code>|nums[i] - x|</code>&nbsp;添加到总代价里。</li>
	<li>将 <code>nums[i]</code>&nbsp;变为&nbsp;<code>x</code>&nbsp;。</li>
</ul>

如果一个正整数正着读和反着读都相同，那么我们称这个数是&nbsp;回文数&nbsp;。比方说，<code>121</code>&nbsp;，<code>2552</code> 和&nbsp;<code>65756</code>&nbsp;都是回文数，但是&nbsp;<code>24</code>&nbsp;，<code>46</code>&nbsp;，<code>235</code>&nbsp;都不是回文数。

如果一个数组中的所有元素都等于一个整数&nbsp;<code>y</code>&nbsp;，且&nbsp;<code>y</code>&nbsp;是一个小于&nbsp;<code>109</code>&nbsp;的&nbsp;回文数&nbsp;，那么我们称这个数组是一个 等数数组&nbsp;。

请你返回一个整数，表示执行任意次特殊操作后使 <code>nums</code>&nbsp;成为 等数数组&nbsp;的 最小&nbsp;总代价。

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,3,4,5]
输出：6
解释：我们可以将数组中所有元素变为回文数 3 得到等数数组，数组变成 [3,3,3,3,3] 需要执行 4 次特殊操作，代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6 。
将所有元素变为其他回文数的总代价都大于 6 。
</pre>

示例 2：

<pre>
输入：nums = [10,12,13,14,15]
输出：11
解释：我们可以将数组中所有元素变为回文数 11 得到等数数组，数组变成 [11,11,11,11,11] 需要执行 5 次特殊操作，代价为 |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11 。
将所有元素变为其他回文数的总代价都大于 11 。
</pre>

示例 3 ：

<pre>
输入：nums = [22,33,22,33,22]
输出：22
解释：我们可以将数组中所有元素变为回文数 22 得到等数数组，数组变为 [22,22,22,22,22] 需要执行 2 次特殊操作，代价为 |33 - 22| + |33 - 22| = 22 。
将所有元素变为其他回文数的总代价都大于 22 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>