HackerRank - Project Euler #6 - Sum Square Difference

Read the problem statement here:

Project Euler: https://projecteuler.net/problem=6

HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler006/problem

We can find the sum of squares of N numbers by this closed form formula:
\[\sum_{i=1}^{N} i = \dfrac{N(N+1)(2N+1)}{6}\]
You can study the proof of this formula here. The series is known as square pyramidal number sequence.

And, the closed formula for finding the sum of N numbers is:
\[\sum_{i=1}^{N} i = \dfrac{N(N+1)}{2}\]
Proof is here. The series is known as triangular number sequence.

The advantage of using these two formulas instead of simply solving it iteratively is it saves time. We can loop from i=1 to i=N and for each iteration we can do the following:
  • Sum += i
  • SumSquares += i * i
But that's an \(O(n)\) logic. Why not make it cooler by using a \(O(1)\) trick?

My Solution in Java:


Note: Test Case 1 will fail if you use int datatype for n. I made that mistake. After searching a bit, I found a good explanation. Read it here.

The time complexity of the program is \(O(1)\).

It passed all the testcases on HackerRank.




Comments