Project Euler : Problem 6 - Sum square difference

Problem Statement : Sum square difference

Problem 6 : The sum of the squares of the first ten natural numbers is,

$$1^2 + 2^2 + ... + 10^2 = 385$$

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

$$(1 + 2 + ... + 10)^2 = 552 = 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.

Concept and Theory

The sum of square of first $n$ terms of natural number is given as follows,

$$(1^2 + 2^2 + \dots + n^2) \ = \ \frac{n(n+1)(2n+1)}{6}$$

And sum of first $n$ terms of natural number is given as follows,

$$(1+2+ \dots + n) \ = \ \frac{n(n+1)}{2}$$

We are asked,

$$=\Bigg ( \frac{n(n+1)}{2} \Bigg )^2 - \frac{n(n+1)(2n+1)}{6}$$ $$=\frac{n(n+1)}{2} \Bigg [ \frac{n(n+1)}{2} \ - \ \frac{2n+1}{3} \Bigg]$$ $$=\frac{n(n+1)}{2} \Bigg [ \frac{3n^2+3n-4n-2}{6} \Bigg]$$ $$=\frac{n(n+1)}{2} \Bigg [ \frac{3n^2-n-2}{6} \Bigg]$$ $$=\frac{n(n+1)}{2} \Bigg [ \frac{(3n+2)(n-1)}{6} \Bigg]$$ $$=\frac{n(n+1)(n-1)(3n+2)}{12}$$

Code

/**
 * A function that calculates the absolute difference between the sum of the
 * squares of the first natural numbers and the square of the sum.
 *
 * @param num
 *            : the last number in the series
 *
 * @return result
 */
public static long sumSquareDifference(long num) {
  long result = (num * (num - 1) * (num + 1) * (3 * num + 2)) / 12;
  return result;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as above method $sumSquareDifference$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler