Sorting: Given an array, return the number of steps required to make array elements same

Problem Statement:

You are given an array, you need to return the minimum number of steps to make the array elements same.

You can increment or decrement element of the array by 1.

Example:

Input: arr = [1, 2, 3]

Output: 2

[1, 2, 3] => [2, 2, 3] => [2, 2, 2]

Solution Explanation:

we will use sorting technique to solve the problem.

First we will sort the array.

Then we need to increase the left side of the array and then decrease the right side of the array.

We need to make them equal to the center element to get the result.

Time Complexity: O(n logn) for sort + O(n) for loop = O(n logn) Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int solution(vector<int>& nums) 
{
    sort(nums.begin(),nums.end());
    
    int n = nums.size();
    int median = n/2;
    
    int res = 0;
    
    for(int i=0;i<n;i++)
    {
        res += abs(nums[i]-nums[median]);
    }
    
    return res;
}


int main() 
{
    vector<int> arr = {1, 2, 3, 4};

    cout<<solution(arr);
    
    return 0;
}

Output

4