Minimum cost to make array equalindromic

Array Math Binary Search Greedy Sorting

23.3% acceptance

Feb 25, 2026

244

100

You are given a 0-indexed integer array nums having length n. You are allowed to perform a special move any number of times on nums. In one special move you perform the following steps: Choose an index i in the range [0, n - 1], and a positive integer x. Add |nums[i] - x| to the total cost. Change the value of nums[i] to x. A palindromic number stays the same when its digits are reversed. An array is considered equalindromic if all the elements are equal to a palindromic number y (y < 10^9). Return an integer denoting the minimum possible total cost.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_cost(nums: Vec<i32>) -> i64 {
    let mut sorted: Vec<i64> = nums.iter().map(|&x| x as i64).collect();
    sorted.sort_unstable();
    let n = sorted.len();

    // Prefix sums for O(1) cost(target) = sum of |sorted[i] - target|
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + sorted[i];
    }
    let total = prefix[n];

    let cost = |target: i64| -> i64 {
      // pos = number of elements <= target
      let pos = sorted.partition_point(|&x| x <= target);
      // left part: target * pos - prefix[pos]
      // right part: (total - prefix[pos]) - target * (n - pos) as i64
      target * pos as i64 - prefix[pos]
        + (total - prefix[pos]) - target * (n - pos) as i64
    };

    let median = sorted[n / 2];
    let candidates = Self::palindrome_candidates(median);
    candidates.iter().map(|&p| cost(p)).min().unwrap()
  }

  // Generate ~5 palindrome candidates arithmetically near `n`, no string allocation.
  fn palindrome_candidates(n: i64) -> Vec<i64> {
    let len = n.ilog10() as usize + 1;
    let half = (len + 1) / 2;
    let divisor = 10i64.pow((len - half) as u32);
    let base_prefix = n / divisor;
    let min_prefix = 10i64.pow(half as u32 - 1);
    let max_prefix = 10i64.pow(half as u32);

    let mut result = Vec::with_capacity(5);

    for delta in -1i64..=1 {
      let p = base_prefix + delta;
      if p < min_prefix || p >= max_prefix {
        continue;
      }
      let palindrome = Self::make_palindrome(p, len);
      if palindrome >= 1 && palindrome <= 1_000_000_000 {
        result.push(palindrome);
      }
    }

    // Boundary palindromes handle digit-length transitions:
    //   lower: 9, 99, 999, ...  upper: 11, 101, 1001, ...
    if len > 1 {
      let low = 10i64.pow(len as u32 - 1) - 1;
      if low >= 1 {
        result.push(low);
      }
    }
    let high = 10i64.pow(len as u32) + 1;
    if high <= 1_000_000_000 {
      result.push(high);
    }

    result.sort_unstable();
    result.dedup();
    result
  }

  // Mirror the given prefix into a full palindrome of `total_len` digits (pure arithmetic).
  fn make_palindrome(prefix: i64, total_len: usize) -> i64 {
    let half = (total_len + 1) / 2;
    let mut p = prefix;
    // For odd length skip the middle digit when mirroring
    let mut rev = if total_len % 2 == 1 { prefix / 10 } else { prefix };
    for _ in 0..(total_len - half) {
      p = p * 10 + rev % 10;
      rev /= 10;
    }
    p
  }
}