Difference between square of sum of numbers and sum of square of numbers.

An algorithm to find the difference between the square of the sum of numbers and the sum of the square of numbers.

We will find the square of the sum of numbers(1 + 2 + 3 … 10 = 55 ^ 2) and the sum of the square of numbers (1 ^ 2 + 2 ^ 2 + … 10 ^ 2).

Example

Input:
10

Output:
2640

We are going to use two different methods to solve this problem.

  • We are going to use a loop to find the square of sum and sum of squares of numbers that will take O(n).
  • Using a mathematical formula that will run in O(1).
  • Everything will be written in ES6.

Using a loop O(n).

Implementation

  • We are going to loop from 1 to n and calulate the sum as well as sum of the sqaure of number using different variables.
  • Then we will return the difference.
 let diff = (num) => {
   let sum = 0, squareSum = 0;
   
   //calculate the sum and squareSum
   for(let i = 1; i <= num; i++){
       sum = sum + i;
       squareSum = squareSum + (i * i);
   }
   
   return (sum * sum) - squareSum;
 }
Input:
console.log(diff(10));
console.log(diff(25));
console.log(diff(97));

Output:
2640
100100
22282064

Time complexity: O(n).
Space complexity: O(1).

Time and Space complexity

  • We are iterating from 1 to n and calculating the sum and squareSum, so Time complexity is O(n).
  • We are using constant space, so Space complexity is O(1).

Using mathematical formula

Implementation

  • We are going to use mathematical formulas to calulate the square of sum and sum of square of given number.
  • Sum of number from 1 to n: (n * (n + 1)) / 2.
  • Sum of Square of numbers from 1 to n: (n * (n + 1) * ((n * 2) + 1)) / 6.
 let diff = (num) => {
   let sum = 0, squareSum = 0;
   sum = (num * (num + 1)) / 2;
   squareSum = (num * (num + 1) * ((num * 2) + 1)) / 6;
   return (sum * sum) - squareSum;
 }
Input:
console.log(diff(10));
console.log(diff(25));
console.log(diff(97));

Output:
2640
100100
22282064

Time complexity: O(1).
Space complexity: O(1).

Time and Space complexity

  • We are using mathematical formulas for calculating the sum and squareSum, so Time complexity is O(1).
  • We are using constant space, so Space complexity is O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *