4053. Minimum Operations to Make Every Element Palindromic

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 2.

Return the minimum number of operations required to make every element in nums a positive palindrome. Different elements may be changed into different palindromic integers.

Example 1:

Input: nums = [10,12,14,16]

Output: 9

Explanation:

One optimal sequence of operations is:

Decrement nums[0] by 2 once to change it from 10 to 8.
Decrement nums[1] by 2 twice to change it from 12 to 8.
Decrement nums[2] by 2 three times to change it from 14 to 8.
Increment nums[3] by 2 three times to change it from 16 to 22.

After 1 + 2 + 3 + 3 = 9 operations, nums = [8, 8, 8, 22], and every element is a positive palindromic integer.

It can be shown that fewer than 9 operations cannot achieve this.

Example 2:

Input: nums = [9,10,11,10]

Output: 2

Explanation:

Decrement nums[1] and nums[3] by 2 once each.

After 2 operations, nums = [9, 8, 11, 8], and every element is a positive palindromic integer.

At least one operation is needed for each of these two elements, so the minimum number of operations is 2.

Example 3:

Input: nums = [125]

Output: 2

Explanation:

Decrement nums[0] by 2 twice to change it from 125 to 121, which is a positive palindromic integer.

A single operation would change it to 123 or 127, neither of which is palindromic. Thus, the minimum number of operations is 2.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solutions

Solution 1: Precompute Palindromes + Binary Search

Thinking

Each operation adds or subtracts $2$, so parity never changes: $\textit{nums}[i]$ can only become a positive palindrome of the same parity. The elements are independent, and the answer is the sum of each value’s distance to the nearest same-parity palindrome, divided by $2$.

With $n = 10^5$ and values up to $10^9$, walking from $x$ by steps of $2$ until a palindrome appears is too slow.

Every palindrome is a mirrored prefix. Enumerating prefixes $1 \ldots 10^5$ and forming both even-length and odd-length palindromes covers everything around $10^9$. Split them by parity, sort each list, and binary-search the nearest neighbor for every $x$.

An operation increments or decrements an element by $2$, so its parity is invariant and the target palindrome must have the same parity. The elements are independent: for each $x$, find the nearest same-parity positive palindrome $p$ and add $\lvert x - p \rvert / 2$.

During preprocessing, enumerate prefixes $i = 1, 2, \ldots, 10^5$ and let $s$ be the decimal representation of $i$:

Even-length palindrome: $s + \mathrm{reverse}(s)$
Odd-length palindrome: $s + \mathrm{reverse}(s[:-1])$

Store them in two lists by parity and sort each list. This range covers all palindromes with up to about $12$ digits, which is enough for values up to $10^9$.

For each $x$, binary-search the first palindrome that is at least $x$ in the same-parity list, compare it with the previous one, and take the smaller distance divided by $2$.

Let $M$ be the number of palindromes (about $2 \times 10^5$). Preprocessing takes $O(M \log M)$ and each query takes $O(\log M)$. The overall time complexity is $O(M \log M + n \log M)$, and the space complexity is $O(M)$.

class Solution {
    static List<Long>[] ps = new ArrayList[2];

    static {
        ps[0] = new ArrayList<>();
        ps[1] = new ArrayList<>();
        for (int i = 1; i <= 100000; i++) {
            String s = String.valueOf(i);
            String t1 = new StringBuilder(s).reverse().toString();
            String t2 = new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString();
            long x = Long.parseLong(s + t1);
            ps[(int) (x & 1)].add(x);
            long y = Long.parseLong(s + t2);
            ps[(int) (y & 1)].add(y);
        }
        ps[0].sort(Long::compare);
        ps[1].sort(Long::compare);
    }

    public long minOperations(int[] nums) {
        long ans = 0;
        for (int x : nums) {
            List<Long> p = ps[x & 1];
            int l = 0, r = p.size();
            while (l < r) {
                int m = (l + r) >>> 1;
                if (p.get(m) < x) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            long t = Long.MAX_VALUE;
            if (l < p.size()) {
                t = p.get(l) - x;
            }
            if (l > 0) {
                t = Math.min(t, (long) x - p.get(l - 1));
            }
            ans += t / 2;
        }
        return ans;
    }
}

class Solution {
public:
    long long minOperations(vector<int>& nums) {
        static vector<long long> ps[2];
        if (ps[0].empty()) {
            for (long long i = 1; i <= 100000; ++i) {
                string s = to_string(i);
                string t1 = s;
                reverse(t1.begin(), t1.end());
                string t2 = s.substr(0, s.size() - 1);
                reverse(t2.begin(), t2.end());
                long long x = stoll(s + t1);
                ps[x & 1].push_back(x);
                long long y = stoll(s + t2);
                ps[y & 1].push_back(y);
            }
            sort(ps[0].begin(), ps[0].end());
            sort(ps[1].begin(), ps[1].end());
        }
        long long ans = 0;
        for (int x : nums) {
            auto& p = ps[x & 1];
            auto it = lower_bound(p.begin(), p.end(), x);
            long long t = LLONG_MAX;
            if (it != p.end()) {
                t = *it - x;
            }
            if (it != p.begin()) {
                t = min(t, (long long) x - *prev(it));
            }
            ans += t / 2;
        }
        return ans;
    }
};

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


class Solution:
    def minOperations(self, nums: list[int]) -> int:
        ans = 0
        for x in nums:
            p = ps[x & 1]
            i = bisect_left(p, x)
            t = inf
            if i < len(p):
                t = p[i] - x
            if i:
                t = min(t, x - p[i - 1])
            ans += t // 2
        return ans

var ps [2][]int64

func init() {
	for i := int64(1); i <= 100000; i++ {
		s := strconv.FormatInt(i, 10)
		t1 := reverse(s)
		t2 := reverse(s[:len(s)-1])
		x, _ := strconv.ParseInt(s+t1, 10, 64)
		ps[x&1] = append(ps[x&1], x)
		y, _ := strconv.ParseInt(s+t2, 10, 64)
		ps[y&1] = append(ps[y&1], y)
	}
	sort.Slice(ps[0], func(a, b int) bool { return ps[0][a] < ps[0][b] })
	sort.Slice(ps[1], func(a, b int) bool { return ps[1][a] < ps[1][b] })
}

func reverse(s string) string {
	b := []byte(s)
	for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
		b[i], b[j] = b[j], b[i]
	}
	return string(b)
}

func minOperations(nums []int) int64 {
	var ans int64
	for _, x := range nums {
		p := ps[x&1]
		i := sort.Search(len(p), func(i int) bool { return p[i] >= int64(x) })
		t := int64(1 << 62)
		if i < len(p) {
			t = p[i] - int64(x)
		}
		if i > 0 {
			t = min(t, int64(x)-p[i-1])
		}
		ans += t / 2
	}
	return ans
}

const ps: number[][] = [[], []];

for (let i = 1; i <= 10 ** 5; i++) {
    const s = String(i);
    const t1 = [...s].reverse().join('');
    const t2 = [...s.slice(0, -1)].reverse().join('');
    const x = Number(s + t1);
    ps[x & 1].push(x);
    const y = Number(s + t2);
    ps[y & 1].push(y);
}
ps[0].sort((a, b) => a - b);
ps[1].sort((a, b) => a - b);

function minOperations(nums: number[]): number {
    let ans = 0;
    for (const x of nums) {
        const p = ps[x & 1];
        let l = 0;
        let r = p.length;
        while (l < r) {
            const m = (l + r) >> 1;
            if (p[m] < x) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        let t = Number.MAX_SAFE_INTEGER;
        if (l < p.length) {
            t = p[l] - x;
        }
        if (l > 0) {
            t = Math.min(t, x - p[l - 1]);
        }
        ans += Math.floor(t / 2);
    }
    return ans;
}

4053 - Minimum Operations to Make Every Element Palindromic

4053. Minimum Operations to Make Every Element Palindromic

Description

Solutions

Solution 1: Precompute Palindromes + Binary Search

All Problems

All Solutions

Welcome to Subscribe On Youtube

4053. Minimum Operations to Make Every Element Palindromic

Description

Solutions

Solution 1: Precompute Palindromes + Binary Search

All Problems

All Solutions