Project Euler 6: Sum Square Difference

Problem

The sum of the squares of the first ten natural numbers is,

1²+2²+…+10²=385

The square of the sum of the first ten natural numbers is,

(1+2+…+10)²=55²=3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Official Problem

Solution Approach

In this problem of the Sum Square Difference, we have to find the difference between the square of the sum of natural numbers and the sum of the square of natural numbers. The main part is to find a quick way to find the sum.

In mathematics, we have the formulas of the same which will make our work easy. The formula comes under Arithmetic progression.

The formula to find the sum of the first n natural numbers is :

n(n+1)/2

When we substitute n=100 and square the result, we get the first value in our final difference equation.

The formula to find the sum of squares of first n natural numbers is :

n(n+1)(2n+1)/6

To get the second number which is to be subtracted we substitute n=100 in the formula. In the end, we just subtract the two values to get the final answer.

Time and Space Complexities

The time complexity of the approach is O(1) as it takes constant time to calculate the values. We are using two variables to store the two values hence the space is also constant. The space complexity is O(1).

Coding Approach

Coming to the code part of the approach we first declare the variables which will store the intermediate sums. We then calculate the sums using the formulas discussed above. Lastly, we print the difference between them as the answer.

Solution Code

Java Solution

import java.util.*;

class Solution
{
	public static void main (String[] args)
	{
	  int n=100;
	    
    int squareOfSum = (int)Math.pow(((n*(n+1))/2),2);
    int sumOfSquares = (n*(n+1)*(2*n+1))/6;
        
    System.out.println(squareOfSum - sumOfSquares);
	}
}

import java.util.*;

class Solution

{

public static void main (String[] args)

{

int n=100;

int squareOfSum = (int)Math.pow(((n*(n+1))/2),2);

int sumOfSquares = (n*(n+1)*(2*n+1))/6;

System.out.println(squareOfSum - sumOfSquares);

}

Python Solution

n = 10

square_of_sum = ((n*(n+1))//2)**2
sum_of_squares = n*(n+1)*(2*n + 1) //6

print(square_of_sum - sum_of_squares)

n = 10

square_of_sum = ((n*(n+1))//2)**2

sum_of_squares = n*(n+1)*(2*n + 1) //6

print(square_of_sum - sum_of_squares)

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂