Sum of minimum absolute difference in C++

C++ Program to find sum of minimum absolute difference of the given array

October 12, 2022

Sum of minimum absolute difference in C++

Here, in this page we will discuss sum with minimum absolute difference in C++. We will discuss the two different ways to solve the given problem and compare there time and space complexities.

Here, we will discuss the following two different methods to solve this problem.

Method 1 : Naive Way
Method 2 : Efficient way

Method 1 :

Take a variable say result = INT_MAX, to hold the required minimum sum.
Run an outer loop from index 0 to n,
Create a variable say sum = 0,
Run an inner loop from index 0 to n,
Set, sum += abs(arr[i]-arr[j])
After complete iteration of inner loop set,
result = min(result, sum).
Print result.

Time and Space Complexity :

Time Complexity : O(n²)
Space Complexity : O(1)

Method 1 : Code in C++

//Write a program to find sum of minimum absolute difference of the given array in C++
#include<iostream>
#include<limits/h>
using namespace std;

int main()
{
    int arr[]={2, 4, 5, 3};
    int result = INT_MAX;

    int n = sizeof(arr)/sizeof(arr[0]);

    for(int i=0; i<n; i++){
        int sum =0 ; // variable to hold the sum
        for(int j=0; j<n; j++){
            int x=arr[i]-arr[j];
            if(x<0)
                sum += -x;

            else sum += x;
        }    
    
        if(sum<result)
            result = sum;
        
    }
    cout<<"Minimum Absolute Difference Sum is "<<result;
    return 0;
}

Output

Minimum Absolute Difference Sum is 4

Determine Array is a subset of another array or not

Determine can all numbers of an array be made equal

Sort an array according to the order defined by another array

Replace each element of the array by its rank in the array

Finding equilibrium index of an array

Method 2 :

Sort the array using inbuilt sort function.
Create a variable say median that store the median of the array in it.
If the size of array is even then median= (a[n/2]+a[n/2+1])/2, otherwise median = a[n/2], here a [] is the array and n is the size of the array.
Create a variable say sum that holds the sum in it and initialize it with 0.
Iterate over the array and add the absolute difference in the sum.
Print the sum.

Time and Space Complexity :

Time Complexity : O(nlogn)
Space Complexity : O(1)

Method 2 : Code in C++

//Write a program to find sum of minimum absolute difference of the given array in C++
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int arr[]={2, 4, 5, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

    sort(arr, arr+n);  //sort array

    int median ; //variable to store the median

    if(n%2==0)
    median = ((arr[n/2]+arr[n/2+1])/2);

    else median = arr[n/2];

    int sum =0 ; // variable to hold the sum

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

        int x=arr[i]-median;
        if(x<0)
            sum += -x;

        else sum += x;
    }    
    cout<<"Minimum Absolute Difference Sum is "<<sum;
    return 0;
}

Output

Minimum Absolute Difference Sum is 4

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

One comment on “C++ Program to find sum of minimum absolute difference of the given array”

amanbajpai5734
c++ code:

#include
using namespace std;

int mins(int a, int b)
{
if(a<b)
return a;
return b;
}

int main()
{
int temp=0;
int sum=0;
int arr[9] = {12, 10, 15, 22, 21, 20, 1, 8, 9};
sort(arr,arr+9);
for(int i=0;i<9;i++){
if(i==0)
temp = arr[i+1]-arr[i];
else if(i==8)
temp = arr[i]-arr[i-1];
else
temp = mins(arr[i+1]-arr[i],arr[i]-arr[i-1]);
if(temp<0)
sum+=-temp;
else
sum+=temp;
}
cout<<sum;
return 0;
}

0

Log in to Reply