Given an array arr[] consisting of coordinates of N points on an XY-plane, the task is to find the sum of squared distances between all pairs of points, i.e. (Xi – Xj)2 + (Yi – Yj)2 for every distinct pair (i, j).
Examples:
Input: arr[][] = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}}
Output: 32
Explanation:
Distance of 1st point (1, 1) from the 2nd, 3rd and 4th points are 8, 4 and 4 respectively.
Distance of 2nd point from the 3rd and 4th points are 4 and 4 respectively.
Distance of 3rd point from the 4th point is 8.
Therefore, the total distance = (8 + 4 + 4) + (4 + 4) + (8) = 32Input: arr[][] = {{1, 1}, {1, 1}, {0, 0}}
Output: 4
Explanation:
Distance of 1st point from the 2nd and 3rd points are 0 and 2 respectively.
Distance of 2nd point from the 3rd point is 2.
Therefore, the total distance = (0 + 2) + (2) = 4
Naive Approach: The simplest approach to solve the problem is to generate all possible distinct pairs of the given array arr[][] and calculate the sum of squares of distances between all pairs of points (Xi, Yj) and (Xj, Yj), i.e. (Xi – Xj)2 + (Yi – Yj)2, for every distinct pair (i, j).
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to regroup the sum and split the sum of squares of distances into two sums. Follow the steps below to solve the problem:
- Initialize variables, say xq, yq, xs, and ys.
- Initialize a variable, say res, with zero, to store the resultant sum.
- Traverse the given array and for each point {x, y}, perform the following steps:
- Add the value of (i*x2 + i*y2) in the variable res, which corresponds to adding of squared distance.
- Add the value (xq – 2 * xs * a) and (yq – 2 * ys * b) to res to nullify the effect of the 2 * X * Y in the expansion of (a – b)2.
- Add the values a2 and b2 to variables xq and yq respectively.
- Add the values a and b to variables xs and ys respectively.
- Add the values xs and yq to variables a2 and b2 respectively.
- After completing the above steps, print the value of res as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the sum of squares// of distance between all distinct pairsvoid findSquareSum( int Coordinates[][2], int N){ long long xq = 0, yq = 0; long long xs = 0, ys = 0; // Stores final answer long long res = 0; // Traverse the array for (int i = 0; i < N; i++) { int a, b; a = Coordinates[i][0]; b = Coordinates[i][1]; res += xq; res -= 2 * xs * a; // Adding the effect of this // point for all the previous // x - points res += i * (long long)(a * a); // Temporarily add the // square of x-coordinate xq += a * a; xs += a; res += yq; res -= 2 * ys * b; res += i * (long long)b * b; // Add the effect of this point // for all the previous y - points yq += b * b; ys += b; } // Print the desired answer cout << res;}// Driver Codeint main(){ int arr[][2] = { { 1, 1 }, { -1, -1 }, { 1, -1 }, { -1, 1 } }; int N = sizeof(arr) / sizeof(arr[0]); findSquareSum(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the sum of squares // of distance between all distinct pairs static void findSquareSum( int Coordinates[][], int N) { long xq = 0, yq = 0; long xs = 0, ys = 0; // Stores final answer long res = 0; // Traverse the array for (int i = 0; i < N; i++) { int a, b; a = Coordinates[i][0]; b = Coordinates[i][1]; res += xq; res -= 2 * xs * a; // Adding the effect of this // point for all the previous // x - points res += i * (long)(a * a); // Temporarily add the // square of x-coordinate xq += a * a; xs += a; res += yq; res -= 2 * ys * b; res += i * (long)b * b; // Add the effect of this point // for all the previous y - points yq += b * b; ys += b; } // Print the desired answer System.out.println(res); } // Driver Code public static void main(String[] args) { int arr[][] = { { 1, 1 }, { -1, -1 }, { 1, -1 }, { -1, 1 } }; int N = arr.length; findSquareSum(arr, N); }}// This code is contributed by code_hunt. |
Python3
# Python3 program for the above approach# Function to find the sum of squares# of distance between all distinct pairsdef findSquareSum(Coordinates, N): xq , yq = 0, 0 xs , ys = 0, 0 # Stores final answer res = 0 # Traverse the array for i in range(N): a = Coordinates[i][0] b = Coordinates[i][1] res += xq res -= 2 * xs * a # Adding the effect of this # point for all the previous # x - points res += i * (a * a) # Temporarily add the # square of x-coordinate xq += a * a xs += a res += yq res -= 2 * ys * b res += i * b * b # Add the effect of this point # for all the previous y - points yq += b * b ys += b # Print the desired answer print (res)# Driver Codeif __name__ == '__main__': arr = [ [ 1, 1 ], [ -1, -1 ], [ 1, -1 ], [ -1, 1 ] ] N = len(arr) findSquareSum(arr, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System;class GFG{ // Function to find the sum of squares// of distance between all distinct pairsstatic void findSquareSum(int[,] Coordinates, int N){ long xq = 0, yq = 0; long xs = 0, ys = 0; // Stores final answer long res = 0; // Traverse the array for(int i = 0; i < N ; i++) { int a, b; a = Coordinates[i, 0]; b = Coordinates[i, 1]; res += xq; res -= 2 * xs * a; // Adding the effect of this // point for all the previous // x - points res += i * (long)(a * a); // Temporarily add the // square of x-coordinate xq += a * a; xs += a; res += yq; res -= 2 * ys * b; res += i * (long)b * b; // Add the effect of this point // for all the previous y - points yq += b * b; ys += b; } // Print the desired answer Console.Write(res);} // Driver code static void Main() { int[,] arr = { { 1, 1 }, { -1, -1 }, { 1, -1 }, { -1, 1 } }; int N = arr.GetLength(0); findSquareSum(arr, N);}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program for the above approach // Function to find the sum of squares // of distance between all distinct pairs function findSquareSum( Coordinates, N) { let xq = 0, yq = 0; let xs = 0, ys = 0; // Stores final answer let res = 0; // Traverse the array for (let i = 0; i < N; i++) { let a, b; a = Coordinates[i][0]; b = Coordinates[i][1]; res += xq; res -= 2 * xs * a; // Adding the effect of this // point for all the previous // x - points res += i * (a * a); // Temporarily add the // square of x-coordinate xq += a * a; xs += a; res += yq; res -= 2 * ys * b; res += i * b * b; // Add the effect of this point // for all the previous y - points yq += b * b; ys += b; } // Print the desired answer document.write(res); }// Driver code let arr = [[ 1, 1 ], [ -1, -1 ], [ 1, -1 ], [ -1, 1 ]]; let N = arr.length; findSquareSum(arr, N); </script> |
Output:
32
Time Complexity: O(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!
