Back

3229. Minimum Cost to Make Array Equalindromic

Medium
Array
Math
Binary Search
Greedy
Sorting
Solve on LeetCode View Solutions

Description

You are given an integer array nums.

In one operation, you may choose an index i and either increment or decrement nums[i] by 1.

Return the minimum number of operations required to make every element in nums equal to the same positive palindromic integer.

 

Example 1:

Input: nums = [1,2,3,4,5]
Output: 6
Explanation: Increment nums[0] twice and nums[1] once, then decrement nums[3] once and nums[4] twice. After 6 operations, nums becomes [3,3,3,3,3], and 3 is a positive palindromic integer.
It can be shown that this is the minimum number of operations required.

Example 2:

Input: nums = [10,12,13,14,15]
Output: 11
Explanation: Increment nums[0] once, then decrement nums[1], nums[2], nums[3], and nums[4] by 1, 2, 3, and 4, respectively. After 11 operations, nums becomes [11,11,11,11,11], and 11 is a positive palindromic integer.
It can be shown that this is the minimum number of operations required.

Example 3:

Input: nums = [22,33,22,33,22]
Output: 22
Explanation: Decrement nums[1] and nums[3] by 11 each. After 22 operations, nums becomes [22,22,22,22,22], and 22 is a positive palindromic integer.
It can be shown that this is the minimum number of operations required.

 

Constraints:

  • 1 <= n <= 105
  • 1 <= nums[i] <= 109

Hints

Hint 1
Find the median of <code>nums</code> after sorting it (if the length is even, we can select any number from the two in the middle). Let’s call it <code>m</code>.
Hint 2
Try the smallest palindromic number that is larger than or equal to <code>m</code> (if any) and the largest palindromic number that is smaller than or equal to <code>m</code> (if any). These two values are the candidate palindromic numbers for values of all indices.
Hint 3
We can use math constructions to construct the two palindromic numbers in <code>O(log(m) / 2)</code> time or we can do it using brute-force by starting from m and checking smaller and larger values in <code>O(sqrt(10<sup>log(m)</sup>))</code>.
Hint 4
It is also possible to just generate all palindromic numbers using recursion in <code>O(sqrt(10<sup>9</sup>log(10<sup>9</sup>))</code>.

Similar Questions

Minimum Moves to Equal Array Elements II
Medium
Minimum Cost to Make Array Equal
Hard
Minimum Operations to Make Every Element Palindromic
Medium

Statistics

Acceptance
23.6%
Submissions
72,247
Accepted
17,039