# 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);
```

### Sharecodepoint

Sharecodepoint is the junction where every essential thing is shared for college students in the well-defined packets of codes. We are focused on providing you the best material package like Question papers, MCQ'S, and one NIGHT STUDY MATERIAL. facebook twitter youtube instagram