Minimum Cost to Make Array Equalindromic solution and explanation

def generate_palindromes(limit):
    palindromes = []
    for length in range(1, 10):
        for first_half in range(10**(length-1), 10**length):
            s = str(first_half)
            palindromes.append(int(s + s[-2::-1]))  # Odd length
            palindromes.append(int(s + s[::-1]))    # Even length
            palindromes = [p for p in palindromes if p < limit]
    return palindromes


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

nums = [1, 2, 3, 4, 5]
print(min_cost_to_equalindromic(nums))

import java.util.*;

class Solution {
    public int minCostToEqualindromic(int[] nums) {
        List<Integer> palindromes = generatePalindromes(1000000000);
        int minCost = Integer.MAX_VALUE;

        for (int p : palindromes) {
            int cost = 0;
            for (int num : nums) {
                cost += Math.abs(num - p);
            }
            minCost = Math.min(minCost, cost);
        }
        return minCost;
    }

    private List<Integer> generatePalindromes(int limit) {
        List<Integer> palindromes = new ArrayList<>();
        for (int length = 1; length < 10; length++) {
            int start = (int)Math.pow(10, length - 1);
            int end = (int)Math.pow(10, length);
            for (int first_half = start; first_half < end; first_half++) {
                String s = Integer.toString(first_half);
                String sReverse = new StringBuilder(s).reverse().toString();
                palindromes.add(Integer.parseInt(s + sReverse.substring(1)));
                if (Integer.parseInt(s + sReverse) < limit) {
                    palindromes.add(Integer.parseInt(s + sReverse));
                }
            }
        }
        return palindromes;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println(sol.minCostToEqualindromic(nums));
    }
}

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;
    }
};

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;
}

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
}

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

        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
    }
}