In one step, any element of a given array can be either increased or decreased by 1.

{getToc} $title={Table of Contents}

In one step, any element of a given array can be either increased or decreased by 1.

Write a function:

class Solution { 
public int solution(int[] A); 
}

that, given an array A of N integers, returns the minimum number of steps required to make all elements equal.

Examples:

1. Given A = [3, 2, 1, 1, 2, 3, 1], the function should return 5. All 1s can be increased by 1 and all 3s can be decreased by 1.

2. Given A = [4, 1, 4, 1], the function should return 6. All 4s can be decreased by 1 three times.

3. Given A = [3, 3, 3], the function should return 0. All elements are already the same.

Write an <b><b>efficient</b></b> algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [1..4].

Solution Java:

import java.util.Arrays;

public class Solution {

    public static int solution(int A[]){

   
        int  minSteps = 0;

   
        int totalEle = A.length;

     
        Arrays.sort(A);

        int midElement = A[totalEle / 2];

        for (int i = 0; i < totalEle; ++i)
            minSteps += Math.abs(A[i] - midElement);

     
        if (totalEle % 2 == 0) {
            int tempCost = 0;

            midElement = A[(totalEle / 2) - 1];

            
            for (int i = 0; i < totalEle; ++i)
                tempCost += Math.abs(A[i] - midElement);

      
            minSteps = Math.min(minSteps, tempCost);
        }

       
        return minSteps;
    }


    public static void main(String[] args)
    {
        int A[] = {3,2,1,1,2,3,1};

        int B[] = {4,1,4,1};

        
        int C[] = {3,3,3};

        System.out.println(solution(A));

        System.out.println("\n" + solution(B));

        System.out.println("\n" + solution(C));

    }
}

Solution JavaScript:

function solution(A) {
    let i,j;
    let S = [];
 
for ( var y = 0; y < R; y++ ) {
    S[ y ] = [];
    for ( var x = 0; x < C; x++ ) {
        S[ y ][ x ] = 0;
    }
}
    let max_of_s, max_i, max_j;
     
    /* Set first column of S[][]*/
    for(i = 0; i < R; i++)
        S[i][0] = A[i][0];
     
    /* Set first row of S[][]*/
    for(j = 0; j < C; j++)
        S[0][j] = A[0][j];
         
    /* Construct other entries of S[][]*/
    for(i = 1; i < R; i++)
    {
        for(j = 1; j < C; j++)
        {
            if(A[i][j] == 1)
                S[i][j] = Math.min(S[i][j-1],Math.min( S[i-1][j],
                                S[i-1][j-1])) + 1;
            else
                S[i][j] = 0;
        }
    }
     
    /* Find the maximum entry, and indexes of maximum entry
        in S[][] */
    max_of_s = S[0][0]; max_i = 0; max_j = 0;
    for(i = 0; i < R; i++)
    {
        for(j = 0; j < C; j++)
        {
            if(max_of_s < S[i][j])
            {
                max_of_s = S[i][j];
                max_i = i;
                max_j = j;
            }
        }            
    }
 
    document.write("Maximum size sub-matrix is: 
");
    for(i = max_i; i > max_i - max_of_s; i--)
    {
        for(j = max_j; j > max_j - max_of_s; j--)
        {
            document.write( A[i][j] , " ");
        }
        document.write("
");
    }
}
 
 
/* Driver code */
let A = [[0, 1, 1, 0, 1],
         [1, 1, 0, 1, 0],
         [0, 1, 1, 1, 0],
         [1, 1, 1, 1, 0],
         [1, 1, 1, 1, 1],
         [0, 0, 0, 0, 0]];
                     
solution(A);