Count number of pair of elements whose difference is smaller than average difference

Given an array of positive integers we have to find number of pair of elements whose difference is smaller than average difference. Average difference is defined as (max(A)-min(A))/(n-1), where A is the array and max(A),min(A) is the maximum and minimum element of the array.

Examples:

Input : {9,3,10,2,3}
Output : 2

Input : {7,9,5,3,1}
Output : 0

Approach:

The above problem can be solved by arranging the elements the given array and then two nested for loop to check the difference of each element with remaining ones. If the difference is smaller than average difference than increase the value of count.

Implementation:

C++

// CPP program to count pairs of elements whose 
// difference is smaller than the average difference
#include<bits/stdc++.h>
using namespace std;

int countPairs(int arr[], int n)
{
    // Elements are arranged in ascending order
    sort(arr, arr + n);
    
    // Calculate the average difference of the array 
    int avg = (int)((arr[n - 1] - arr[0]) / (n - 1));
    
    int count = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(abs(arr[i] - arr[j]) < avg)
                count++;
        }
    }
    
    return count;
}

// Driver code
int main()
{
    int arr[] = {9, 13, 10, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countPairs(arr, n);
    
    return 0;
}

Java

// JAVA program to count pairs of elements whose 
// difference is smaller than the average difference
import java.util.*;

public class Cpp {
    public static int countPairs(int arr[], int n) {
        // Elements are arranged in ascending order
        Arrays.sort(arr);

        // Calculate the average difference of the array 
        int avg = (arr[n - 1] - arr[0]) / (n - 1);

        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(arr[i] - arr[j]) < avg)
                    count++;
            }
        }
        return count;
    }

    // Driver code
    public static void main(String[] args) {
        int arr[] = {9, 13, 10, 2, 3};
        int n = arr.length;
        System.out.println(countPairs(arr, n));
    }
}

Output:

Time complexity: O(nlogn)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.