Given an array arr[] containing N integers, the task is to calculate the average of the difference between both elements in pairs formed from given N integers.
Examples:
Input: arr[] = {-1, 3, -5, 4}
Output: 5.166667
Explanation: There are 6 possible pair of points in the given array with the pairwise difference as: diff(-1, 3) = 4, diff(-1, -5) = 4, diff(-1, 4) = 5, diff(3, -5) = 8, diff(3, 4) = 1, diff(-5, 4) = 9. Therefore, average pairwise difference is (4 + 4 + 5 + 8 + 1 + 9)/6 = 31/6 = 5.166667.Input: arr[] = { -1, 2, -3, 7, -6 }
Output: 6.2
Approach: This problem can be solved by using the Greedy Approach and prefix sum method. If the points in the array arr[] are in sorted order, then the sum of distances of ith point to all the greater points can be calculated as: (arr[i+1] – arr[i]) + (arr[i+2] – arr[i]) … + (arr[N-1] – arr[i]) => (arr[i+1] + arr[i+2]… + arr[N-1]) – arr[i] * (N – 1 – i). Using this observation, the given problem can be solved using the following steps:
- Initially sort the array arr[] in non-decreasing order.
- Create a prefix sum array pre[] of the array arr[].
- Iterate through every index i and add (pre[N – 1] – pre[i]) – arr[i] * (N – 1 – i) into a variable ans.
- The required answer is ans / count of pairs => ans / (N*(N-1)/2).
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find average distance// between given points on a linelong double averageDistance( vector<int> arr, int N){ // Sorting the array arr[] sort(arr.begin(), arr.end()); // Stores the prefix sum // array of arr[] int pre[N] = { 0 }; pre[0] = arr[0]; // Loop to calculate prefix sum for (int i = 1; i < N; i++) { pre[i] = pre[i - 1] + arr[i]; } // Initialising the answer variable long double ans = 0; // Loop to iterate through arr[] for (int i = 0; i < N - 1; i++) { // Adding summation of all // distances from ith point ans += (pre[N - 1] - pre[i]) - arr[i] * (N - 1 - i); } // Return Average return ans / ((N * (N - 1)) / 2);}// Driver Codeint main(){ vector<int> arr = { -1, 3, -5, 4 }; cout << averageDistance(arr, arr.size()); return 0;} |
Java
// Java implementation for the above approachimport java.util.*;class GFG { // Function to find average distance // between given points on a line static double averageDistance(int[] arr, int N) { // Sorting the array arr[] Arrays.sort(arr); // Stores the prefix sum // array of arr[] int[] pre = new int[N]; pre[0] = arr[0]; // Loop to calculate prefix sum for (int i = 1; i < N; i++) { pre[i] = pre[i - 1] + arr[i]; } // Initialising the answer variable double ans = 0; // Loop to iterate through arr[] for (int i = 0; i < N - 1; i++) { // Adding summation of all // distances from ith point ans += (pre[N - 1] - pre[i]) - arr[i] * (N - 1 - i); } // Return Average ans = (ans / ((N * (N - 1)) / 2)); return ans; } // Driver Code public static void main(String[] args) { int[] arr = { -1, 3, -5, 4 }; System.out.print(String.format( "%.5f", averageDistance(arr, arr.length))); }}// This code is contributed by ukasp. |
Python3
# Python3 program for above approach# Function to find average distance# between given points on a linedef averageDistance(arr, N): # Sorting the array arr[] arr.sort() # Stores the prefix sum # array of arr[] pre = [0 for _ in range(N)] pre[0] = arr[0] # Loop to calculate prefix sum for i in range(1, N): pre[i] = pre[i - 1] + arr[i] # Initialising the answer variable ans = 0 # Loop to iterate through arr[] for i in range(0, N - 1): # Adding summation of all # distances from ith point ans += ((pre[N - 1] - pre[i]) - (arr[i] * (N - 1 - i))) # Return Average return ans / ((N * (N - 1)) / 2)# Driver Codeif __name__ == "__main__": arr = [ -1, 3, -5, 4 ] print(averageDistance(arr, len(arr)))# This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;class GFG{// Function to find average distance// between given points on a linestatic double averageDistance( int []arr, int N){ // Sorting the array arr[] Array.Sort(arr); // Stores the prefix sum // array of arr[] int []pre = new int[N]; pre[0] = arr[0]; // Loop to calculate prefix sum for (int i = 1; i < N; i++) { pre[i] = pre[i - 1] + arr[i]; } // Initialising the answer variable double ans = 0; // Loop to iterate through arr[] for (int i = 0; i < N - 1; i++) { // Adding summation of all // distances from ith point ans += (pre[N - 1] - pre[i]) - arr[i] * (N - 1 - i); } // Return Average ans = Math.Round((ans / ((N * (N - 1)) / 2)), 5); return ans;}// Driver Codepublic static void Main(){ int []arr = { -1, 3, -5, 4 }; Console.Write(averageDistance(arr, arr.Length));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find average distance // between given points on a line function averageDistance( arr, N) { // Sorting the array arr[] arr.sort(function (a, b) { return a - b }) // Stores the prefix sum // array of arr[] let pre = new Array(N).fill(0); pre[0] = arr[0]; // Loop to calculate prefix sum for (let i = 1; i < N; i++) { pre[i] = pre[i - 1] + arr[i]; } // Initialising the answer variable let ans = 0; // Loop to iterate through arr[] for (let i = 0; i < N - 1; i++) { // Adding summation of all // distances from ith point ans += (pre[N - 1] - pre[i]) - arr[i] * (N - 1 - i); } // Return Average return ans / ((N * (N - 1)) / 2); } // Driver Code let arr = [-1, 3, -5, 4]; document.write(averageDistance(arr, arr.length).toPrecision(6)); // This code is contributed by Potta Lokesh </script> |
Output
5.16667
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
