In this tutorial, we are going to find the Minimum Cost to Make Array Equalindromic in Java. Equalindromic Array: An "equalindromic" array is a specific form of palindrome array in which all entries are identical. The "Minimum Cost to Make Array Equalindromic" task is to determine the lowest cost required to change an array into an equalindromic array, where all members are identical while minimizing the total cost of such transformations. Let's see a few examples to understand it. In the input, a 0 – 0-indexed array is provided.

Example 1:

Input: numbArr = {3, 4, 5, 6, 7}

Output: 6

Explanation: By assigning the palindromic number five to each element of the array, we may make it equalindromic. By using 5 special moves to change the array to [5, 5, 5, 5, 5], the cost is [3 - 5| + |4 - 5| + |5 - 5| + |6 - 5| + |7 - 5| = 6. It can be demonstrated that there is no cheaper way to change all elements to a palindromic number other than 5.

Example 2:

Input: numbArr = {22, 33, 44, 55, 66}

Output: 66

Explanation: By altering every element in the array to the palindromic number 55, we may make it equalindromic. The sum of |22 - 55| + |33 - 55| + |44 - 55| + |55 - 55| + |66 - 55| = 66 represents the cost of converting the array to [55, 55, 55, 55, 55] using 5 special moves. It has been demonstrated that altering all elements to any palindromic number other than 55 cannot be done at a cheaper cost.

Example 3:

Input: numbArr = { 44, 33, 44, 33, 44}

Output: 22

Explanation: A palindromic number, 33, can be used to make all of the array's elements equalindromic. The sum of |33 - 33| + |44 - 33| + |33 - 33| + |44 - 33| + |33 - 33| = 22 is the cost of converting the array to [33, 33, 33, 33, 33] with 5 special moves. It has been demonstrated that altering all elements to any palindromic number other than 33 cannot be done at a cheaper cost.

Approach: Using Greedy Algorithm

In this approach, we use a combination of techniques, including sorting, palindrome checking, and dynamic programming. First of all, define two methods called verifyPalindromic to check given input is palindromic or not and minCost to return the minimum cost. Let’s initialize an array called numb and sort it in ascending order using Arrays.sort(). Now, initialize variables called p1 and p2 to store the median values and cost1 and cost2 with 0 to costs for two possible equildromic arrays. Calculate the median using two variables, p1 and p2 and find equildromic arrays by decrementing and incrementing them until a palindromic number is found using a loop statement called while loop. After that, iterate through each element of the array using a loop statement like for loop. Let's store the value of the absolute difference between each element and p1 in cost1 and store the value of the absolute difference between each element and p2 in cost2. Finally, return the minimum cost between cost1 and cost2 using the Math.min method.

FileName: MinCostForEquildromicArray.java

// importing Arrays class

import java.util.Arrays;

public class MinCostForEquildromicArray {

    boolean verifyPalindromic(long x){

        String strg=Long.toString(x); //convert number to string

        int p1=0,p2=strg.length()-1;

        while(p1<p2){ //loop to check string palindromic

            if(strg.charAt(p1)!=strg.charAt(p2)){

                  return false;

            }

            p1++;

            p2--;

        }

        return true;

    }

    // minimum cost method to get min cost to make array eualindromic

    public long minCost(int[] numb) {

        int i,n=numb.length;

        long median;

        Arrays.sort(numb); //sorting

        if(n%2!=0){

            median=1L*numb[n/2];

        }

        else{

            median=((numb[n/2]+numb[(n/2 -1)])/2)*1L;

        }

        long cost1=0,cost2=0;

        long p1=median,p2=median;

        while(!verifyPalindromic(p1)){

            p1--;

        }

        while(!verifyPalindromic(p2)){

            p2++;

        }

        for(i=0;i<n;i++){

            cost1+=1L*Math.abs(numb[i]-p1);

            cost2+=1L*Math.abs(numb[i]-p2);

        }

        return Math.min(cost1,cost2);

    }

    //main method

    public static void main(String[] args) {

        MinCostForEquildromicArray e = new MinCostForEquildromicArray();

        int[] numb = {4, 5, 6, 7, 8}; // provide input values

        System.out.println("Minimum cost to make array equalindromic: " + e.minCost(numb));

    }

}

Output:

Minimum cost to make array equalindromic: 6

Complexity Analysis: The program uses a Greedy Algorithm to determine the minimum cost for transforming an array into an equalindromic array. The program takes O(n log n) and O(log n) time complexity for sorting and for checking palindrome, respectively. Also, for calculating the cost by iteration, each element takes O(n) time. Therefore, the overall time complexity is O(n log n), where n is the array size. The space complexity is O(n) because for storing an input array of size n.

← Prev Next →