Tutorialspoint.dev

Sum of pairwise products

For given any unsigned int n find the final value of &Sum;(i*j) where (1<=i<=n) and (i <= j <= n).

Examples:

Input : n = 3
Output : 25
We get the sum as following. Note that
first term i varies from 1 to 3 and second
term values from value of first term to n.
1*1 + 1*2 + 1*3 + 2*2 + 2*3 + 3*3 = 25

Input : 5
Output : 140


Method 1 (Simple) We run two loops and compute the required sum.

C++

// Simple CPP program to find sum 
// of given series.
#include <bits/stdc++.h>
using namespace std;
  
long long int findSum(int n)
{
   long long int sum = 0;
   for (int i=1; i<=n; i++)
     for (int j=i; j<=n; j++)
        sum = sum + i*j;
   return sum;
}
  
int main()
{
    int n = 5;
    cout << findSum(n);
    return 0;
}

Java

// Simple Java program to find sum 
// of given series.
class GFG {
      
    static int findSum(int n)
    {
        int sum = 0;
          
        for (int i=1; i<=n; i++)
            for (int j=i; j<=n; j++)
                sum = sum + i*j;
                  
        return sum;
    }
      
    // Driver code
    public static void main(String[] args)
    {
          
        int n = 5;
          
        System.out.println(findSum(n));
    }
}
  
// This code is contributed by Smitha Dinesh Semwal.

Python3

   
# Simple Python3 program to   
# find sum of given series.
  
def findSum(n) :
    sm = 0
    for i in range(1, n + 1) :
        for j in range(i, n + 1) :
            sm = sm + i * j
              
    return sm
      
# Driver Code
n = 5
print(findSum(n))
  
# This code is contributed by Nikita Tiwari.

/div>

C#

// Simple C# program to find sum 
// of given series.
class GFG {
      
    static int findSum(int n)
    {
        int sum = 0;
          
        for (int i=1; i<=n; i++)
            for (int j=i; j<=n; j++)
                sum = sum + i*j;
                  
        return sum;
    }
      
    // Driver code
    public static void Main()
    {
          
        int n = 5;
          
        System.Console.WriteLine(findSum(n));
    }
}
  
// This code is contributed by mits.

PHP

<?php
// Simple PHP program to find sum 
// of given series.
  
function findSum($n)
{
    $sum = 0;
    for ($i = 1; $i <= $n; $i++)
        for ($j = $i; $j <= $n; $j++)
            $sum = $sum + $i * $j;
    return $sum;
}
  
// Driver Code
$n = 5;
echo findSum($n);
  
// This code is contributed by mits
?>

Output:

140

Time Complexity: O(n^2).

Method 2 (Better)
We can observe following in the given problem.
1 is multiplied with all numbers from 1 to n.
2 is multiplied with all numbers from 2 to n.
………………………………………
………………………………………
i is multiplied with all numbers from i to n.

We compute sum of first n natural numbers which is our first term. For remaining terms, we multiply i with sum of numbers from i to n. We keep track of this sum by subtracting i from initial sum in every iteration.

C++

// Efficient CPP program to find sum 
// of given series.
#include <bits/stdc++.h>
using namespace std;
  
long long int findSum(int n)
{
   long long int multiTerms = n * (n + 1) / 2;
  
   // Sum of multiples of 1 is 1 * (1 + 2 + ..)
   long long int sum = multiTerms;
  
   // Adding sum of multiples of numbers other
   // than 1, starting from 2.
   for (int i=2; i<=n; i++)
   {
       // Subtract previous number
       // from current multiple. 
       multiTerms = multiTerms - (i - 1);
  
       // For example, for 2, we get sum 
       // as (2 + 3 + 4 + ....) * 2
       sum = sum + multiTerms * i;
   }
   return sum;
}
  
// Driver code
int main()
{
    int n = 5;
    cout << findSum(n);
    return 0;
}

Java

// Efficient Java program to find sum 
// of given series.
class GFG {
      
    static int findSum(int n)
    {
          
        int multiTerms = n * (n + 1) / 2;
          
        // Sum of multiples of 1 is 1 * (1 + 2 + ..)
        int sum = multiTerms;
          
        // Adding sum of multiples of numbers other
        // than 1, starting from 2.
        for (int i = 2; i <= n; i++)
        {
              
            // Subtract previous number
            // from current multiple. 
            multiTerms = multiTerms - (i - 1);
          
            // For example, for 2, we get sum 
            // as (2 + 3 + 4 + ....) * 2
            sum = sum + multiTerms*i;
        }
          
        return sum;
    }
      
    // Driver code
    public static void main(String[] args)
    {
          
        int n = 5;
          
        System.out.println(findSum(n));
    }
}
  
// This code is contributed by Smitha Dinesh Semwal.

Python3

   
# Efficient Python3 program 
# to find sum of given series.
  
def findSum(n) :
    multiTerms = n * (n + 1) // 2
      
    # Sum of multiples of 1 is 1 * (1 + 2 + ..)
    sm = multiTerms
  
    # Adding sum of multiples of numbers 
    # other than 1, starting from 2.
    for i in range(2, n+1) :
          
        # Subtract previous number
        # from current multiple. 
        multiTerms = multiTerms - (i - 1)
      
        # For example, for 2, we get sum 
        # as (2 + 3 + 4 + ....) * 2
        sm = sm + multiTerms * i
      
    return sm
      
# Driver code
n = 5
print(findSum(n))
  
# This code is contributed by Nikita Tiwari.

C#

// C# program to find sum 
// of given series.
using System;
class GFG {
      
    static int findSum(int n)
    {
          
        int multiTerms = n * (n + 1) / 2;
          
        // Sum of multiples of 1 is 1 * (1 + 2 + ..)
        int sum = multiTerms;
          
        // Adding sum of multiples of numbers other
        // than 1, starting from 2.
        for (int i = 2; i <= n; i++)
        {
              
            // Subtract previous number
            // from current multiple. 
            multiTerms = multiTerms - (i - 1);
          
            // For example, for 2, we get sum 
            // as (2 + 3 + 4 + ....) * 2
            sum = sum + multiTerms*i;
        }
          
        return sum;
    }
      
    // Driver code
    public static void Main()
    {
          
        int n = 5;
          
        Console.WriteLine(findSum(n));
    }
}
  
// This code is contributed by Mukul Singh. 

PHP

<?php
// Efficient PHP program to find sum 
// of given series.
  
function findSum($n)
{
    $multiTerms = (int)($n * ($n + 1) / 2);
  
// Sum of multiples of 1 is 1 * (1 + 2 + ..)
$sum = $multiTerms;
  
// Adding sum of multiples of numbers other
// than 1, starting from 2.
for ($i=2; $i<=$n; $i++)
{
    // Subtract previous number
    // from current multiple. 
    $multiTerms = $multiTerms - ($i - 1);
  
    // For example, for 2, we get sum 
    // as (2 + 3 + 4 + ....) * 2
    $sum = $sum + $multiTerms * $i;
}
return $sum;
}
  
// Driver code
  
    $n = 5;
    echo findSum($n);
  
//This code is contributed by mits
?>

Output:

140

Time Complexity: O(n).

Method 3 (Efficient)
The whole calculation can be done in the O(1) time as there is a closed form expression for the sum. Let i and j run from 1 through n. We want to compute S = sum(i*j) over all i and j such that i <= j otherwise we would have duplicates such as 2*3 + …+3*2; on the other hand, having i = j is OK which gives us 2*2 + … This is all by the problem specification. (Sorry if my notation is bizarre.)

Now, there are two kinds of terms in the sum S: those with i = j (squares, denoted S1) and those with i j always, but the value is the same, by symmetry: 2 * S2 = (sum i)^2 – sum (i^2) . Note that 2*S2 = S3 – S1 as the latter sum is just S1; the former sum (denoted S3) is new here, but there is a closed form solution for it too. We can now eliminate the mixed term completely: S = S1 + S2 = (S1 + S3) / 2.

Since sum(i) = n*(n+1)/2, we get S3 = n*n*(n+1)*(n+1)/4 ; likewise for the sum of squares: S1 = n*(2*n+1)*(n+1)/6. The final expression simplifies to:
S = n*(n+1)*(n+2)*(3*n+1)/24 . (As an exercise, you may want to prove that the numerator is indeed divisible by 24.)

C++

// Efficient CPP program to find sum 
// of given series.
#include <bits/stdc++.h>
using namespace std;
  
long long int findSum(int n)
{
   return n*(n+1)*(n+2)*(3*n+1)/24;
}
  
// Driver code
int main()
{
    int n = 5;
    cout << findSum(n);
    return 0;
}

Java

// Efficient Java program to find sum 
// of given series.
class GFG {
      
    static int findSum(int n)
    {
        return n * (n + 1) * (n + 2) * 
                                 (3 * n + 1) / 24;
    }
      
    // Driver code
    public static void main(String[] args)
    {
          
        int n = 5;
          
        System.out.println(findSum(n));
    }
}
  
// This code is contributed by Smitha Dinesh Semwal.

Python3

# Efficient Python3 program to find  
# sum of given series.
  
def findSum(n):
  
    return n * (n + 1) * (n + 2) * (3 * n + 1) / 24
  
# Driver code
n = 5
print(int(findSum(n)))
  
# This code is contributed by Smitha Dinesh Semwal.

C#

// Efficient C# program 
// to find sum of given 
// series.
using System;
  
class GFG
{
static int findSum(int n)
{
    return n * (n + 1) * (n + 2) * 
                 (3 * n + 1) / 24;
}
  
// Driver code
static public void Main ()
{
    int n = 5;
      
    Console.WriteLine(findSum(n));
}
}
  
// This code is contributed
// by ajit.

PHP

<?php
// Efficient PHP 
// program to find sum 
// of given series.
  
function findSum($n)
{
    return $n * ($n + 1) * 
           ($n + 2) * (3 * 
           $n + 1) / 24;
}
  
// Driver code
$n = 5;
echo findSum($n);
  
// This code is contrubuted 
// by akt_mit
?>

Output:

140

Time Complexity: O(1).

Thanks to diprey1 for suggesting this efficient solution.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter