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).