2967. Minimum Cost to Make Array Equalindromic

SourceWeekly Contest 376 Q3DifficultyMediumRating2116

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 <= 10⁵
1 <= nums[i] <= 10⁹

Solutions

Solution 1: Preprocessing + Sorting + Binary Search

Thinking

All values become one palindrome; the \(L_1\) cost is minimized near the median. Palindromes are generated by mirroring halves in \([1,10^5]\) and stored in sorted \(ps\).

Sort \(\textit{nums}\), binary-search \(ps\) around the median, and evaluate a few neighbors. \(n \le 10^5\), so the target is not enumerated exhaustively.

The range of palindrome numbers in the problem is \([1, 10^9]\). Due to the symmetry of palindrome numbers, we can enumerate in the range of \([1, 10^5]\), then reverse and concatenate them to get all palindrome numbers. Note that if it is an odd-length palindrome number, we need to remove the last digit before reversing. The array of palindrome numbers obtained by preprocessing is denoted as \(ps\). We sort the array \(ps\).

Next, we sort the array \(\textit{nums}\) and take the median \(x\) of \(\textit{nums}\). We only need to find a number in the palindrome array \(ps\) that is closest to \(x\) through binary search, and then calculate the cost of \(\textit{nums}\) becoming this number to get the answer.

The time complexity is \(O(n \log n)\), and the space complexity is \(O(M)\), where \(n\) is the length of the array \(\textit{nums}\), and \(M\) is the length of the palindrome array \(ps\).

Similar problems:

906. Super Palindromes

Python3JavaC++GoTypeScriptRust

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]
    t2 = s[:-1][::-1]
    ps.append(int(s + t1))
    ps.append(int(s + t2))
ps.sort()


class Solution:
    def minimumCost(self, nums: list[int]) -> int:
        def f(x: int) -> int:
            return sum(abs(v - x) for v in nums)

        nums.sort()
        i = bisect_left(ps, nums[len(nums) // 2])
        return min(f(ps[j]) for j in range(i - 1, i + 2) if 0 <= j < len(ps))

public class Solution {
    private static long[] ps;
    private int[] nums;

    static {
        ps = new long[2 * (int) 1e5];
        for (int i = 1; i <= 1e5; i++) {
            String s = Integer.toString(i);
            String t1 = new StringBuilder(s).reverse().toString();
            String t2 = new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString();
            ps[2 * i - 2] = Long.parseLong(s + t1);
            ps[2 * i - 1] = Long.parseLong(s + t2);
        }
        Arrays.sort(ps);
    }

    public long minimumCost(int[] nums) {
        this.nums = nums;
        Arrays.sort(nums);
        int i = Arrays.binarySearch(ps, nums[nums.length / 2]);
        i = i < 0 ? -i - 1 : i;
        long ans = 1L << 60;
        for (int j = i - 1; j <= i + 1; j++) {
            if (0 <= j && j < ps.length) {
                ans = Math.min(ans, f(ps[j]));
            }
        }
        return ans;
    }

    private long f(long x) {
        long ans = 0;
        for (int v : nums) {
            ans += Math.abs(v - x);
        }
        return ans;
    }
}

using ll = long long;

ll ps[2 * 100000];

int init = [] {
    for (int i = 1; i <= 100000; i++) {
        string s = to_string(i);
        string t1 = s;
        reverse(t1.begin(), t1.end());
        string t2 = s.substr(0, s.length() - 1);
        reverse(t2.begin(), t2.end());
        ps[2 * i - 2] = stoll(s + t1);
        ps[2 * i - 1] = stoll(s + t2);
    }
    sort(ps, ps + 2 * 100000);
    return 0;
}();

class Solution {
public:
    long long minimumCost(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i = lower_bound(ps, ps + 2 * 100000, nums[nums.size() / 2]) - ps;
        auto f = [&](ll x) {
            ll ans = 0;
            for (int& v : nums) {
                ans += abs(v - x);
            }
            return ans;
        };
        ll ans = LLONG_MAX;
        for (int j = i - 1; j <= i + 1; j++) {
            if (0 <= j && j < 2 * 100000) {
                ans = min(ans, f(ps[j]));
            }
        }
        return ans;
    }
};

var ps [2 * 100000]int64

func init() {
    for i := 1; i <= 100000; i++ {
        s := strconv.Itoa(i)
        t1 := reverseString(s)
        t2 := reverseString(s[:len(s)-1])
        ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
        ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
    }
    sort.Slice(ps[:], func(i, j int) bool {
        return ps[i] < ps[j]
    })
}

func reverseString(s string) string {
    cs := []rune(s)
    for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
        cs[i], cs[j] = cs[j], cs[i]
    }
    return string(cs)
}

func minimumCost(nums []int) int64 {
    sort.Ints(nums)
    i := sort.Search(len(ps), func(i int) bool {
        return ps[i] >= int64(nums[len(nums)/2])
    })

    f := func(x int64) int64 {
        var ans int64
        for _, v := range nums {
            ans += int64(abs(int(x - int64(v))))
        }
        return ans
    }

    ans := int64(math.MaxInt64)
    for j := i - 1; j <= i+1; j++ {
        if 0 <= j && j < len(ps) {
            ans = min(ans, f(ps[j]))
        }
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

const ps = Array(2e5).fill(0);

const init = (() => {
    for (let i = 1; i <= 1e5; ++i) {
        const s: string = i.toString();
        const t1: string = s.split('').reverse().join('');
        const t2: string = s.slice(0, -1).split('').reverse().join('');
        ps[2 * i - 2] = parseInt(s + t1, 10);
        ps[2 * i - 1] = parseInt(s + t2, 10);
    }
    ps.sort((a, b) => a - b);
})();

function minimumCost(nums: number[]): number {
    const search = (x: number): number => {
        let [l, r] = [0, ps.length];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (ps[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    const f = (x: number): number => {
        return nums.reduce((acc, v) => acc + Math.abs(v - x), 0);
    };

    nums.sort((a, b) => a - b);
    const i: number = search(nums[nums.length >> 1]);
    let ans: number = Number.MAX_SAFE_INTEGER;
    for (let j = i - 1; j <= i + 1; j++) {
        if (j >= 0 && j < ps.length) {
            ans = Math.min(ans, f(ps[j]));
        }
    }
    return ans;
}

impl Solution {
    pub fn minimum_cost(nums: Vec<i32>) -> i64 {
        use std::cmp::min;
        use std::sync::Once;

        static INIT: Once = Once::new();
        static mut PS: Vec<i64> = Vec::new();

        INIT.call_once(|| {
            let mut ps_local = Vec::with_capacity(2 * 100_000);
            for i in 1..=100_000 {
                let s = i.to_string();

                let mut t1 = s.clone();
                t1 = t1.chars().rev().collect();
                ps_local.push(format!("{}{}", s, t1).parse::<i64>().unwrap());

                let mut t2 = s[0..s.len() - 1].to_string();
                t2 = t2.chars().rev().collect();
                ps_local.push(format!("{}{}", s, t2).parse::<i64>().unwrap());
            }
            ps_local.sort();
            unsafe {
                PS = ps_local;
            }
        });

        let mut nums = nums;
        nums.sort();

        let mid = nums[nums.len() / 2] as i64;

        let i = unsafe {
            match PS.binary_search(&mid) {
                Ok(i) => i,
                Err(i) => i,
            }
        };

        let f = |x: i64| -> i64 { nums.iter().map(|&v| (v as i64 - x).abs()).sum() };

        let mut ans = i64::MAX;

        for j in i.saturating_sub(1)..=(i + 1).min(2 * 100_000 - 1) {
            let x = unsafe { PS[j] };
            ans = min(ans, f(x));
        }

        ans
    }
}

2967. Minimum Cost to Make Array Equalindromic

Description

Solutions

Solution 1: Preprocessing + Sorting + Binary Search

Comments