Given an array arr[] of size N, the task is to compute the sum of squares of differences of all possible pairs.
Examples:
Input: arr[] = {2, 8, 4}
Output: 56
Explanation:
Sum of squared differences of all possible pairs = (2 – 8)2 + (2 – 4)2 + (8 – 4)2 = 56Input: arr[] = {-5, 8, 9, -4, -3}
Output: 950
Brute Force Approach:
The brute force approach to solve this problem is to use nested loops to generate all possible pairs of elements from the given array and then calculate the square of the difference between each pair. Finally, we can sum up all the squared differences to get the desired output.
Here are the steps of approach:
- Initialize a variable sum to 0 to keep track of the running sum of squared differences.
- Use nested loops to generate all possible pairs of elements from the given array. The outer loop will iterate through all the elements of the array, and the inner loop will start from the next element and go till the end of the array. This ensures that we generate all possible pairs of elements.
- For each pair of elements, calculate the difference between them and square the result. Add this squared difference to the running sum.
- After the loops have finished iterating through all possible pairs of elements, output the value of the sum variable. This will be the sum of squared differences of all possible pairs of elements in the given array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of squares// of differences of all possible pairsvoid sumOfSquaredDifferences(int arr[], int N){ int sum = 0; // Nested loops to generate all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Calculating the square of the difference between the pairs int diff = arr[i] - arr[j]; sum += (diff * diff); } } // Output the sum of squared differences of all possible pairs cout << sum << endl;}// Driver Codeint main(){ // Given array int arr[] = { 2, 8, 4 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function call to find sum of square // of differences of all possible pairs sumOfSquaredDifferences(arr, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static void main(String[] args) { // Given array int arr[] = { 2, 8, 4 }; // Size of the array int N = arr.length; // Function call to find sum of square // of differences of all possible pairs sumOfSquaredDifferences(arr, N); } public static void sumOfSquaredDifferences(int arr[], int N) { int sum = 0; // Nested loops to generate all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Calculating the square of the difference // between the pairs int diff = arr[i] - arr[j]; sum += (diff * diff); } } // Output the sum of squared differences of all // possible pairs System.out.println(sum); }}//This code is contributed by aeroabrar_31 |
Python3
#Code in python for the above approach# Function to calculate the sum of squares of differences of all possible pairsdef sumOfSquaredDifferences(arr): N = len(arr) sum = 0 # Nested loops to generate all possible pairs for i in range(N): for j in range(i + 1, N): # Calculating the square of the difference between the pairs diff = arr[i] - arr[j] sum += (diff * diff) # Output the sum of squared differences of all possible pairs print(sum)# Driver codeif __name__ == "__main__": # Given array arr = [2, 8, 4] # Function call to find the sum of square # of differences of all possible pairs sumOfSquaredDifferences(arr) |
C#
using System;class GFG{ public static void Main(string[] args) { // Given array int[] arr = { 2, 8, 4 }; // Size of the array int N = arr.Length; // Function call to find sum of square // of differences of all possible pairs SumOfSquaredDifferences(arr, N); } public static void SumOfSquaredDifferences(int[] arr, int N) { int sum = 0; // Nested loops to generate all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Calculating the square of the difference // between the pairs int diff = arr[i] - arr[j]; sum += (diff * diff); } } // Output the sum of squared differences of all // possible pairs Console.WriteLine(sum); }}//This code is contributed by aeroabrar_31 |
Javascript
function sumOfSquaredDifferences(arr) { let sum = 0; // Nested loops to generate all possible pairs for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { // Calculating the square of the difference between the pairs const diff = arr[i] - arr[j]; sum += diff * diff; } } // Output the sum of squared differences of all possible pairs console.log(sum);}// Given arrayconst arr = [2, 8, 4];// Function call to find sum of square of differences of all possible pairssumOfSquaredDifferences(arr); |
Output
56
Time Complexity: O(N^2) since we use nested loops to generate all possible pairs of elements.
Space Complexity: O(1) as we are not using any extra space.
Efficient Approach: The optimal idea is based on rearranging the expression in the following manner:
∑i=2 n ∑j=1i-1 (Ai-Aj)2
Since Ai – Ai = 0, the above expression can be rearranged as 1/2*(∑i=1n ∑j=1n (Ai-Aj)2) which can be further be simplified using the identity:
(A – B)2 = A2 + B2 – 2 * A * B
As 1/2*(∑i=1n ∑j=1n (Ai2 + Aj2 – 2*Ai*Aj)) = 1/2 * (2*n*∑i=1n Ai2 – 2*∑i=1n (Aj * ∑j=1n Aj))
The final expression is n*∑i=1n Ai2 – (∑i=1nAi)2 which can be computed by linearly iterating over the array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of squares// of differences of all possible pairsvoid sumOfSquaredDifferences(int arr[], int N){ // Stores the final sum int ans = 0; // Stores temporary values int sumA = 0, sumB = 0; // Traverse the array for (int i = 0; i < N; i++) { sumA += (arr[i] * arr[i]); sumB += arr[i]; } sumA = N * sumA; sumB = (sumB * sumB); // Final sum ans = sumA - sumB; // Print the answer cout << ans;}// Driver Codeint main(){ // Given array int arr[] = { 2, 8, 4 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function call to find sum of square // of differences of all possible pairs sumOfSquaredDifferences(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to calculate sum of squares// of differences of all possible pairsstatic void sumOfSquaredDifferences(int arr[], int N){ // Stores the final sum int ans = 0; // Stores temporary values int sumA = 0, sumB = 0; // Traverse the array for(int i = 0; i < N; i++) { sumA += (arr[i] * arr[i]); sumB += arr[i]; } sumA = N * sumA; sumB = (sumB * sumB); // Final sum ans = sumA - sumB; // Print the answer System.out.println(ans);}// Driver Codepublic static void main (String[] args){ // Given array int arr[] = { 2, 8, 4 }; // Size of the array int N = arr.length; // Function call to find sum of square // of differences of all possible pairs sumOfSquaredDifferences(arr, N);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to calculate sum of squares# of differences of all possible pairsdef sumOfSquaredDifferences(arr, N): # Stores the final sum ans = 0 # Stores temporary values sumA, sumB = 0, 0 # Traverse the array for i in range(N): sumA += (arr[i] * arr[i]) sumB += arr[i] sumA = N * sumA sumB = (sumB * sumB) # Final sum ans = sumA - sumB # Print the answer print(ans)# Driver Codeif __name__ == '__main__': # Given array arr = [2, 8, 4] # Size of the array N = len(arr) # Function call to find sum of square # of differences of all possible pairs sumOfSquaredDifferences(arr, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate sum of squares// of differences of all possible pairsstatic void sumOfSquaredDifferences(int []arr, int N){ // Stores the final sum int ans = 0; // Stores temporary values int sumA = 0, sumB = 0; // Traverse the array for(int i = 0; i < N; i++) { sumA += (arr[i] * arr[i]); sumB += arr[i]; } sumA = N * sumA; sumB = (sumB * sumB); // Final sum ans = sumA - sumB; // Print the answer Console.WriteLine(ans);}// Driver Codepublic static void Main(string[] args){ // Given array int []arr = { 2, 8, 4 }; // Size of the array int N = arr.Length; // Function call to find sum of square // of differences of all possible pairs sumOfSquaredDifferences(arr, N);}}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program for the above approach// Function to calculate sum of squares// of differences of all possible pairsfunction sumOfSquaredDifferences(arr, N){ // Stores the final sum let ans = 0; // Stores temporary values let sumA = 0, sumB = 0; // Traverse the array for(let i = 0; i < N; i++) { sumA += (arr[i] * arr[i]); sumB += arr[i]; } sumA = N * sumA; sumB = (sumB * sumB); // Final sum ans = sumA - sumB; // Print the answer document.write(ans);}// Driver Code// Given arraylet arr = [ 2, 8, 4 ];// Size of the arraylet N = arr.length;// Function call to find sum of square// of differences of all possible pairssumOfSquaredDifferences(arr, N);// This code is contributed by subhammahato348</script> |
Output
56
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!
