Suma de productos por pares

Dado cualquier int sin signo n, encuentre el valor final de ∑(i*j) donde (1<=i<=n) y (i <= j <= n).
Ejemplos: 
 

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

Método 1 (Simple) Ejecutamos dos bucles y calculamos la suma requerida. 
 

// 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;
}

// 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.

# 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.

// 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
// 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
?>

<script>
 
// Simple JavaScript program to find sum
// of given series.
 
    function findSum(n)
    {
        let sum = 0;
           
        for (let i=1; i<=n; i++)
            for (let j=i; j<=n; j++)
                sum = sum + i*j;
                   
        return sum;
    }
 
// Driver Code
 
        let n = 5;
           
        document.write(findSum(n));
 
</script>

140

Complejidad de tiempo: O(n^2).
Método 2 (mejor) 
Podemos observar lo siguiente en el problema dado. 
1 se multiplica por todos los números del 1 al n. 
2 se multiplica por todos los números del 2 al n. 
……………………………………… 
……………………………………… 
i se multiplica con todos los números de i a n.
Calculamos la suma de los primeros n números naturales, que es nuestro primer término. Para los términos restantes, multiplicamos i con la suma de números de i a n. Realizamos un seguimiento de esta suma restando i de la suma inicial en cada iteración.
 

// 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;
}

// 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.

# 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# 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
// 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
?>

<script>
 
    // Javascript program to find
    // sum of given series.
     
    function findSum(n)
    {
          
        let multiTerms = n * (n + 1) / 2;
          
        // Sum of multiples of 1 is 1 * (1 + 2 + ..)
        let sum = multiTerms;
          
        // Adding sum of multiples
        // of numbers other
        // than 1, starting from 2.
        for (let 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;
    }
     
    let n = 5;
          
    document.write(findSum(n));
     
</script>

140

Complejidad temporal: O(n).
Método 3 (Eficiente) 
Todo el cálculo se puede hacer en el tiempo O(1) ya que hay una expresión de forma cerrada para la suma. Sean i y j de 1 a n. Queremos calcular S = sum(i*j) en general i y j tal que i <= j, de lo contrario tendríamos duplicados como 2*3 + …+3*2; por otro lado, tener i = j está bien, lo que nos da 2*2 +… Todo esto es por la especificación del problema. (Lo siento si mi notación es extraña).
Ahora, hay dos tipos de términos en la suma S: aquellos con i = j (cuadrados, denotados S1) y aquellos con ij siempre, pero el valor es el mismo, por simetría: 2 * S2 = (suma i)^2 – suma (i^2) . Tenga en cuenta que 2*S2 = S3 – S1 ya que la última suma es solo S1; la suma anterior (indicada como S3) es nueva aquí, pero también hay una solución de forma cerrada. Ahora podemos eliminar completamente el término mixto: S = S1 + S2 = (S1 + S3) / 2.
Dado que sum(i) = n*(n+1)/2, obtenemos S3 = n*n*(n+ 1)*(n+1)/4 ; igualmente para la suma de cuadrados: S1 = n*(2*n+1)*(n+1)/6. La expresión final se simplifica a: 
S = n*(n+1)*(n+2)*(3*n+1)/24 . (Como ejercicio, es posible que desee probar que el numerador es divisible por 24). 
 

// 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;
}

// 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.

# 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.

// 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
// 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 contributed
// by akt_mit
?>

<script>
 
    // Efficient Javascript program
    // to find sum of given
    // series.
     
    function findSum(n)
    {
        return n * (n + 1) * (n + 2) * (3 * n + 1) / 24;
    }
     
    let n = 5;
      
    document.write(findSum(n));
 
</script>

140

Complejidad Temporal: O(1).
Gracias a diprey1 por sugerir esta eficiente solución.