Difference between square of sum (Σn)² and sum of squares (Σn²)

Reading time: 30 minutes | Coding time: 2 minutes

In this problem, we to need find the difference between the sum of squares of all numbers from 1 to N and the square of the sum of 1 to N. The brute force approach to solve this takes O(N) time complexity but we will solve it in constant time O(1) using an insight.

For example: if N = 3, then:

• Square of sum = (1 + 2 + 3)^2 = 6^2 = 36
• Sum of squares = 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14

Hence, the difference is 36 - 14 = 22.

We will explore two approaches:

• Brute force O(N)
• Efficient approach O(1)

The key idea to solve this problem in constant time is the following two equations (which we have derived further in this article):

F1(N) = 1 + 2 + ... + N = N * (N+1) / 2
F2(N) = 1^2 + 2^2 + ... + N^2 = N * (N+1) * (2*N+1) / 6

Brute force approach

The simplest approach is to add up all values and take the difference. As we are going through each number, this approach takes linear time that is O(N) time complexity.

Pseudocode of brute force approach:

int sum_1 = 0;
int sum_2 = 0;

for(int i = 1; i<=N; i++)
{
    sum_1 += i;
    sum_2 += i*i;
}
answer = sum_1 * sum_1 - sum_2;

Following is the brute force implementation:

class opengenus 
{
    
    static int difference(int N)
    {
        int sum_1 = 0;
        int sum_2 = 0;
        
        for(int i = 1; i<=N; i++)
        {
            sum_1 += i;
            sum_2 += i*i;
        }
        return sum_1 * sum_1 - sum_2;
    }
	public static void main (String[] args) 
	{
		int N = 10;
		int answer = difference(N);
		System.out.println(answer);
	}
}

Output:

2640

Efficient approach

The key insight is that both sum of squares and square of sum follow a pattern and is captured by a mathematical equation. On finding the equation, we can find the respective values instantly and take the difference.

The equations are:

• Sum of 1 to N = N * (N+1) / 2
• Sum of square of 1 to N = (2 * N + 1) * (N + 1) / 6

To understand this better, we will derive the equations.

We will first approach the sum of 1 to N. Let sum of 1 to N = F(N).

F(N) = sum of 1 to N

With this, we understand the following:

F(N)   = 1 + 2 + 3 + ... + (N-1) + N
F(N+1) = 1 + 2 + 3 + ... + (N-1) + N + (N+1)

Now, if we subtract the individual numbers, we get:

F(N) - F(N+1) = - (N+1)
F(N+1) = F(N) + (N+1)

which is intuitive as F(N+1) has one more number than F(N).

If we add the same equation F(N) in reverse, we arrive at this:

F(N) = 1 +   2   + ... + (N-1) + N
F(N) = N + (N-1) + ... +   2   + 1
(+)

2 * F(N) = (N+1) + (N+1) + ... + (N+1) + (N+1)

2 * F(N) = N * (N+1)

F(N) = N * (N+1) / 2

Hence, with this, we arrive at the equation.

Sum of 1 to N = N * (N+1) / 2

Now, we need to find the equation of sum of squares of 1 to N. Let:

F(N) = 1^2 + 2^2 + ... + (N-1)^2 + N^2

We understand the following relation:

F(N+1) = F(N) + (N+1)^2

The easiest way to derive the equation is to use Binomial's technique. Following the following calculations:

   (K-1)^3 = K^3 - 3*K^2 -K + 1 
=> K^3 - (K-1)^3 = 3*K^2 + K - 1  ... EQ(1)

Now, if we place summation for EQ(1), we get the following {EQ(2)}:

$ \sum_{K=1}^N [ K^3 - (K-1)^3 ] = \sum_{K=1}^N 3*K^2 + \sum_{K=1}^N K - \sum_{K=1}^N 1 $

Now, the first part is equal to K^2.

$ \sum_{K=1}^N [ K^3 - (K-1)^3 ] = N^3 $

As

Σ (K^3 - (K-1)^3) = 1^3 - 0^3 + 2^3 - 1^3 + ... + (N^3) - (N-1)^3
  = N^3 (as all other terms are cancelled)

Let us return to EQ(2) with our recent insight:

$ N^3 = \sum_{K=1}^N 3*K^2 + \sum_{K=1}^N K - \sum_{K=1}^N 1 $

$ N^3 = 3 * F_2(N) + F_1(N) + N $

where

F_2(N) = 1^2 + 2^2 + ... + N^2 (our focus)
F_1(N) = 1 + 2 + ... + N = N * (N+1) / 2

$ N^3 = 3 * F_2(N) + N*(N+1)/2 - N $

$ F_2(N) = ( N^3 - N*(N+1)/2 + N )/3 $

$ F_2(N) = ( 2N^3 + N^2 + 3N ) / 6 $

$ F_2(N) = N * (N+1) * (2N+1) / 6 $

Hence, we have arrived at our equation that is:

F_2(N) = N * (N+1) * (2*N+1) / 6

With this, we can find both parts instantly and calculate the difference. Hence, the two equations are:

$ F_1(N) = N * (N+1) / 2 $
$ F_2(N) = N * (N+1) * (2*N+1) / 6 $

With this, our pseudocode will be:

int difference(N)
{
    int sum_1 = N * (N+1) / 2;
    int sum_2 = N * (N+1) * (2*N+1) / 6;
    return sum_1 - sum_2;
}

Following is the implementation:

class opengenus 
{
    static int difference(int N)
    {
        int sum_1 = N * (N+1) / 2;
        int sum_2 = N * (N+1) * (2*N + 1) / 6;
        return sum_1 * sum_1 - sum_2;
    }
	public static void main (String[] args) 
	{
		int N = 10;
		int answer = difference(N);
		System.out.println(answer);
	}
}

Output:

2640

With this, you have the complete idea to solve this problem efficiently in constant time. The ideas you have gained in this problem will help you in solving wider range of problems. Enjoy.