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 faster?
Java code:
import java.util.*; import java.math.*; class Solution{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t– > 0){ long n = in.nextLong(); long Sum = (n * (n + 1)) / 2; long SumSquares = (n * (n + 1) * ((2 * n) + 1)) / 6; long AbsDiff = Math.abs((Sum * Sum) - SumSquares); System.out.println(AbsDiff); } in.close(); } }
Note that Test Case 1 will fail if you use int datatype for n. I made that mistake. I found a good explanation online. Read it here.
The time complexity of the program is \(O(1)\).