Given n number of point in 2-d plane followed by Xi, Yi describing n points. The task is to calculate the hammered distance of n points.
Note: Hammered distance is the sum of the square of the shortest distance between every pair of the point.
Examples:
Input: n = 3
0 1
0 0
1 0
Output: 4Input: n = 4
1 0
2 0
3 0
4 0
Output: 20
Basic Approach:As we have to find out sum of square of shortest distance among all the pairs.So, we can take every possible pair and calculate the sum of square of distance.
// Pseudo code to find hammered-distance using above approach.
//this will store hammered distance
Distance=0
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
//shortest distance between point i and j.
Distance+=(x[i]-x[j])^2+(y[i]-y[j])^2
}
}
Its time complexity will be O(n^2).
Efficient Approach: This problem can be solved in time complexity of O(N).
Below is the implementation of above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Function calculate cumulative sum // of x, y, x^2, y^2 coordinates. void cumm(vector<ll>& x, vector<ll>& y, vector<ll>& cummx, vector<ll>& cummy, vector<ll>& cummx2, vector<ll>& cummy2, ll n) { for (int i = 1; i <= n; i++) { cummx[i] = cummx[i - 1] + x[i]; cummy[i] = cummy[i - 1] + y[i]; cummx2[i] = cummx2[i - 1] + x[i] * x[i]; cummy2[i] = cummy2[i - 1] + y[i] * y[i]; } } // Function ot calculate the hammered distance int calHammeredDistance(int n, vector<ll>& x, vector<ll>& y) { // cummx contains cumulative sum of x // cummy contains cumulative sum of y vector<ll> cummx(n + 1, 0), cummy(n + 1, 0); // cummx2 contains cumulative sum of x^2 // cummy2 contains cumulative sum of y^2 vector<ll> cummx2(n + 1, 0), cummy2(n + 1, 0); // calculate cumulative of x //, y, x^2, y^2, because these terms // required in formula to reduce complexity. // this function calculate all required terms. cumm(x, y, cummx, cummy, cummx2, cummy2, n); // hdx calculate hammer distance for x coordinate // hdy calculate hammer distance for y coordinate ll hdx = 0, hdy = 0; for (int i = 1; i <= n; i++) { // came from formula describe in explanation hdx += (i - 1) * x[i] * x[i] + cummx2[i - 1] - 2 * x[i] * cummx[i - 1]; // came from formula describe in explanation hdy += (i - 1) * y[i] * y[i] + cummy2[i - 1] - 2 * y[i] * cummy[i - 1]; } // total is the sum of both x and y. ll total = hdx + hdy; return total; } // Driver code int main() { // number of points int n = 3; // x contains the x coordinates // y contains the y coordinates //and converting the size to n+1 vector<ll> x = {0, 0, 1, 0}; vector<ll> y = {1, 0, 0, 0}; cout << calHammeredDistance(n, x, y); return 0; } |
Java
// Java implementation of above approachclass GFG{ // Function calculate cumulative sum// of x, y, x^2, y^2 coordinates.static void cumm(int [] x, int [] y, int [] cummx, int [] cummy, int [] cummx2, int [] cummy2, int n){ for (int i = 1; i <= n; i++) { cummx[i] = cummx[i - 1] + x[i]; cummy[i] = cummy[i - 1] + y[i]; cummx2[i] = cummx2[i - 1] + x[i] * x[i]; cummy2[i] = cummy2[i - 1] + y[i] * y[i]; }} // Function ot calculate the hammered distancestatic int calHammeredDistance(int n, int [] x, int [] y){ // cummx contains cumulative sum of x // cummy contains cumulative sum of y int []cummx = new int[n + 1]; int []cummy = new int[n + 1]; // cummx2 contains cumulative sum of x^2 // cummy2 contains cumulative sum of y^2 int []cummx2 = new int[n + 1]; int []cummy2 = new int[n + 1]; // calculate cumulative of x //, y, x^2, y^2, because these terms // required in formula to reduce complexity. // this function calculate all required terms. cumm(x, y, cummx, cummy, cummx2, cummy2, n); // hdx calculate hammer distance for x coordinate // hdy calculate hammer distance for y coordinate int hdx = 0, hdy = 0; for (int i = 1; i <= n; i++) { // came from formula describe in explanation hdx += (i - 1) * x[i] * x[i] + cummx2[i - 1] - 2 * x[i] * cummx[i - 1]; // came from formula describe in explanation hdy += (i - 1) * y[i] * y[i] + cummy2[i - 1] - 2 * y[i] * cummy[i - 1]; } // total is the sum of both x and y. int total = hdx + hdy; return total;} // Driver codepublic static void main(String[] args){ // number of points int n = 3; // x contains the x coordinates // y contains the y coordinates int []x = new int[n + 1]; int []y = new int[n + 1]; x[2] = 1; y[0] = 1; System.out.print(calHammeredDistance(n, x, y)); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the # above approach # Function calculate cumulative sum # of x, y, x^2, y^2 coordinates. def cumm(x, y, cummx, cummy, cummx2, cummy2, n): for i in range(1, n+1): cummx[i] = cummx[i - 1] + x[i] cummy[i] = cummy[i - 1] + y[i] cummx2[i] = cummx2[i - 1] + x[i] * x[i] cummy2[i] = cummy2[i - 1] + y[i] * y[i] # Function ot calculate the # hammered distance def calHammeredDistance(n, x, y): # cummx contains cumulative sum of x # cummy contains cumulative sum of y cummx = [0] * (n + 1) cummy = [0] * (n + 1) # cummx2 contains cumulative sum of x^2 # cummy2 contains cumulative sum of y^2 cummx2 = [0] * (n + 1) cummy2 = [0] * (n + 1) # calculate cumulative of x , y, x^2, y^2, # because these terms are required in the # formula to reduce complexity. # This function calculate all required terms. cumm(x, y, cummx, cummy, cummx2, cummy2, n) # hdx calculate hammer distance for x coordinate # hdy calculate hammer distance for y coordinate hdx, hdy = 0, 0 for i in range(1, n + 1): # came from formula describe in explanation hdx += ((i - 1) * x[i] * x[i] + cummx2[i - 1] - 2 * x[i] * cummx[i - 1]) # came from formula describe in explanation hdy += ((i - 1) * y[i] * y[i] + cummy2[i - 1] - 2 * y[i] * cummy[i - 1]) # total is the sum of both x and y. total = hdx + hdy return total # Driver Codeif __name__ == "__main__": # number of points n = 3 # x contains the x coordinates # y contains the y coordinates x = [0, 0, 1, 0] y = [1, 0, 0, 0] print(calHammeredDistance(n, x, y)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of above approachusing System;class GFG{ // Function calculate cumulative sum// of x, y, x^2, y^2 coordinates.static void cumm(int [] x, int [] y, int [] cummx, int [] cummy, int [] cummx2, int [] cummy2, int n){ for (int i = 1; i <= n; i++) { cummx[i] = cummx[i - 1] + x[i]; cummy[i] = cummy[i - 1] + y[i]; cummx2[i] = cummx2[i - 1] + x[i] * x[i]; cummy2[i] = cummy2[i - 1] + y[i] * y[i]; }} // Function ot calculate the hammered distancestatic int calHammeredDistance(int n, int [] x, int [] y){ // cummx contains cumulative sum of x // cummy contains cumulative sum of y int []cummx = new int[n + 1]; int []cummy = new int[n + 1]; // cummx2 contains cumulative sum of x^2 // cummy2 contains cumulative sum of y^2 int []cummx2 = new int[n + 1]; int []cummy2 = new int[n + 1]; // calculate cumulative of x //, y, x^2, y^2, because these terms // required in formula to reduce complexity. // this function calculate all required terms. cumm(x, y, cummx, cummy, cummx2, cummy2, n); // hdx calculate hammer distance for x coordinate // hdy calculate hammer distance for y coordinate int hdx = 0, hdy = 0; for (int i = 1; i <= n; i++) { // came from formula describe in explanation hdx += (i - 1) * x[i] * x[i] + cummx2[i - 1] - 2 * x[i] * cummx[i - 1]; // came from formula describe in explanation hdy += (i - 1) * y[i] * y[i] + cummy2[i - 1] - 2 * y[i] * cummy[i - 1]; } // total is the sum of both x and y. int total = hdx + hdy; return total;} // Driver codepublic static void Main(String[] args){ // number of points int n = 3; // x contains the x coordinates // y contains the y coordinates int []x = new int[n + 1]; int []y = new int[n + 1]; x[2] = 1; y[0] = 1; Console.Write(calHammeredDistance(n, x, y)); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of above approach // Function calculate cumulative sum // of x, y, x^2, y^2 coordinates. function cumm(x, y, cummx, cummy, cummx2, cummy2, n) { for (var i = 1; i <= n; i++) { cummx[i] = cummx[i - 1] + x[i]; cummy[i] = cummy[i - 1] + y[i]; cummx2[i] = cummx2[i - 1] + x[i] * x[i]; cummy2[i] = cummy2[i - 1] + y[i] * y[i]; } } // Function ot calculate the hammered distance function calHammeredDistance(n, x, y) { // cummx contains cumulative sum of x // cummy contains cumulative sum of y var cummy = new Array(n + 1).fill(0); var cummx = new Array(n + 1).fill(0); // cummx2 contains cumulative sum of x^2 // cummy2 contains cumulative sum of y^2 var cummx2 = new Array(n + 1).fill(0); var cummy2 = new Array(n + 1).fill(0); // calculate cumulative of x //, y, x^2, y^2, because these terms // required in formula to reduce complexity. // this function calculate all required terms. cumm(x, y, cummx, cummy, cummx2, cummy2, n); // hdx calculate hammer distance for x coordinate // hdy calculate hammer distance for y coordinate var hdx = 0, hdy = 0; for (var i = 1; i <= n; i++) { // came from formula describe in explanation hdx += (i - 1) * x[i] * x[i] + cummx2[i - 1] - 2 * x[i] * cummx[i - 1]; // came from formula describe in explanation hdy += (i - 1) * y[i] * y[i] + cummy2[i - 1] - 2 * y[i] * cummy[i - 1]; } // total is the sum of both x and y. var total = hdx + hdy; return total; } // Driver code // number of points var n = 3; // x contains the x coordinates // y contains the y coordinates var x = new Array(n + 1).fill(0); var y = new Array(n + 1).fill(0); x[2] = 1; y[0] = 1; document.write(calHammeredDistance(n, x, y)); </script> |
Output
2
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
