Suma de cuadrados de los primeros n números naturales

Posted on by Rudeus Greyrat

Dado un entero positivo N . La tarea es encontrar 1 2 + 2 2 + 3 2 + ….. + N 2 .

Ejemplos: 

Input : N = 4
Output : 30
12 + 22 + 32 + 42
= 1 + 4 + 9 + 16
= 30

Input : N = 5
Output : 55

Método 1: O(N) La idea es ejecutar un ciclo de 1 an y para cada i, 1 <= i <= n, encontrar i 2 para sumar. 

A continuación se muestra la implementación de este enfoque.  

C++

// CPP Program to find sum of square of first n natural numbers
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of square of first n natural numbers
int squaresum(int n)
{
    // Iterate i from 1 and n
    // finding square of i and add to sum.
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += (i * i);
    return sum;
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << squaresum(n) << endl;
    return 0;
}

Java

// Java Program to find sum of
// square of first n natural numbers
import java.io.*;
 
class GFG {
     
    // Return the sum of square of first n natural numbers
    static int squaresum(int n)
    {
        // Iterate i from 1 and n
        // finding square of i and add to sum.
        int sum = 0;
        for (int i = 1; i <= n; i++)
            sum += (i * i);
        return sum;
    }
      
    // Driven Program
    public static void main(String args[])throws IOException
    {
        int n = 4;
        System.out.println(squaresum(n));
    }
}
 
/*This code is contributed by Nikita Tiwari.*/

Python3

# Python3 Program to
# find sum of square
# of first n natural
# numbers
 
 
# Return the sum of
# square of first n
# natural numbers
def squaresum(n) :
 
    # Iterate i from 1
    # and n finding
    # square of i and
    # add to sum.
    sm = 0
    for i in range(1, n+1) :
        sm = sm + (i * i)
     
    return sm
 
# Driven Program
n = 4
print(squaresum(n))
 
# This code is contributed by Nikita Tiwari.*/

C#

// C# Program to find sum of
// square of first n natural numbers
using System;
 
class GFG {
 
    // Return the sum of square of first
    // n natural numbers
    static int squaresum(int n)
    {
         
        // Iterate i from 1 and n
        // finding square of i and add to sum.
        int sum = 0;
         
        for (int i = 1; i <= n; i++)
            sum += (i * i);
             
        return sum;
    }
 
    // Driven Program
    public static void Main()
    {
        int n = 4;
         
        Console.WriteLine(squaresum(n));
    }
}
 
/* This code is contributed by vt_m.*/

PHP

<?php
// PHP Program to find sum of
// square of first n natural numbers
 
// Return the sum of square of
// first n natural numbers
function squaresum($n)
{
    // Iterate i from 1 and n
    // finding square of i and
    // add to sum.
    $sum = 0;
    for ($i = 1; $i <= $n; $i++)
        $sum += ($i * $i);
    return $sum;
}
 
// Driven Code
$n = 4;
echo(squaresum($n));
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
// Javascript Program to find sum of square of first n natural numbers
 
// Return the sum of square of first n natural numbers
function squaresum(n)
{
    // Iterate i from 1 and n
    // finding square of i and add to sum.
    let sum = 0;
    for (let i = 1; i <= n; i++)
        sum += (i * i);
    return sum;
}
 
// Driven Program
 
    let n = 4;
    document.write(squaresum(n) + "<br>");
 
// This code is contributed by Mayank Tyagi
 
</script>

Producción : 

30

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Método 2: O(1)

Suma de cuadrados de los primeros N números naturales = (N*(N+1)*(2*N+1))/6

Por ejemplo 
, para N=4, Suma = ( 4 * ( 4 + 1 ) * ( 2 * 4 + 1 ) ) / 6 
= 180 / 6 
= 30 
Para N=5, Suma = ( 5 * ( 5 + 1 ) * ( 2 * 5 + 1 ) ) / 6 
= 55

Prueba: 

We know,
(k + 1)3 = k3 + 3 * k2 + 3 * k + 1
We can write the above identity for k from 1 to n:
23 = 13 + 3 * 12 + 3 * 1 + 1 ......... (1)
33 = 23 + 3 * 22 + 3 * 2 + 1 ......... (2)
43 = 33 + 3 * 32 + 3 * 3 + 1 ......... (3)
53 = 43 + 3 * 42 + 3 * 4 + 1 ......... (4)
...
n3 = (n - 1)3 + 3 * (n - 1)2 + 3 * (n - 1) + 1 ......... (n - 1)
(n + 1)3 = n3 + 3 * n2 + 3 * n + 1 ......... (n)

Putting equation (n - 1) in equation n,
(n + 1)3 = (n - 1)3 + 3 * (n - 1)2 + 3 * (n - 1) + 1 + 3 * n2 + 3 * n + 1
         = (n - 1)3 + 3 * (n2 + (n - 1)2) + 3 * ( n + (n - 1) ) + 1 + 1

By putting all equation, we get
(n + 1)3 = 13 + 3 * Σ k2 + 3 * Σ k + Σ 1
n3 + 3 * n2 + 3 * n + 1 = 1 + 3 * Σ k2 + 3 * (n * (n + 1))/2 + n
n3 + 3 * n2 + 3 * n = 3 * Σ k2 + 3 * (n * (n + 1))/2 + n
n3 + 3 * n2 + 2 * n - 3 * (n * (n + 1))/2 = 3 * Σ k2
n * (n2 + 3 * n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k2
n * (n + 1) * (n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k2
n * (n + 1) * (n + 2 - 3/2) = 3 * Σ k2
n * (n + 1) * (2 * n + 1)/2  = 3 * Σ k2
n * (n + 1) * (2 * n + 1)/6  = Σ k2

A continuación se muestra la implementación de este enfoque: 

C++

// CPP Program to find sum
// of square of first n
// natural numbers
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of square of
// first n natural numbers
int squaresum(int n)
{
    return (n * (n + 1) * (2 * n + 1)) / 6;
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << squaresum(n) << endl;
    return 0;
}

Java

// Java Program to find sum
// of square of first n
// natural numbers
import java.io.*;
 
class GFG {
     
    // Return the sum of square
    // of first n natural numbers
    static int squaresum(int n)
    {
        return (n * (n + 1) * (2 * n + 1)) / 6;
    }
     
    // Driven Program
    public static void main(String args[])
                            throws IOException
    {
        int n = 4;
        System.out.println(squaresum(n));
    }
}
 
 
/*This code si contributed by Nikita Tiwari.*/

Python3

# Python3 Program to
# find sum of square
# of first n natural
# numbers
 
# Return the sum of
# square of first n
# natural numbers
def squaresum(n) :
    return (n * (n + 1) * (2 * n + 1)) // 6
 
# Driven Program
n = 4
print(squaresum(n))
 
#This code is contributed by Nikita Tiwari.                                                              

C#

// C# Program to find sum
// of square of first n
// natural numbers
using System;
 
class GFG {
 
    // Return the sum of square
    // of first n natural numbers
    static int squaresum(int n)
    {
        return (n * (n + 1) * (2 * n + 1)) / 6;
    }
 
    // Driven Program
    public static void Main()
 
    {
        int n = 4;
         
        Console.WriteLine(squaresum(n));
    }
}
 
/*This code is contributed by vt_m.*/

PHP

<?php
// PHP Program to find sum
// of square of first n
// natural numbers
 
// Return the sum of square of
// first n natural numbers
function squaresum($n)
{
    return ($n * ($n + 1) *
           (2 * $n + 1)) / 6;
}
 
// Driven Code
$n = 4;
echo(squaresum($n));
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
// Javascript program to find sum
// of square of first n
// natural numbers
 
// Return the sum of square of
// first n natural numbers
function squaresum(n)
{
    return parseInt((n * (n + 1) *
                     (2 * n + 1)) / 6);
}
 
// Driver code
let n = 4;
 
document.write(squaresum(n));
 
// This code is contributed by rishavmahato348
 
</script>

Producción :  

30

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra

Evitar el desbordamiento temprano: 
para n grande, el valor de (n * (n + 1) * (2 * n + 1)) se desbordaría. Podemos evitar el desbordamiento hasta cierto punto utilizando el hecho de que n*(n+1) debe ser divisible por 2. 

C++

// CPP Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of square of first n natural
// numbers
int squaresum(int n)
{
    return (n * (n + 1) / 2) * (2 * n + 1) / 3;
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << squaresum(n) << endl;
    return 0;
}

Python3

# Python Program to find sum of square of first
# n natural numbers. This program avoids
# overflow upto some extent for large value
# of n.y
 
def squaresum(n):
    return (n * (n + 1) / 2) * (2 * n + 1) / 3
 
# main()
n = 4
print(squaresum(n));
 
# Code Contributed by Mohit Gupta_OMG <(0_o)>

Java

// Java Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
 
import java.io.*;
import java.util.*;
 
class GFG
{
    // Return the sum of square of first n natural
    // numbers
public static int squaresum(int n)
{
    return (n * (n + 1) / 2) * (2 * n + 1) / 3;
}
 
    public static void main (String[] args)
    {
        int n = 4;
    System.out.println(squaresum(n));
    }
}
 
// Code Contributed by Mohit Gupta_OMG <(0_o)>

C#

// C# Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
 
using System;
 
class GFG {
     
    // Return the sum of square of
    // first n natural numbers
    public static int squaresum(int n)
    {
        return (n * (n + 1) / 2) * (2 * n + 1) / 3;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 4;
         
        Console.WriteLine(squaresum(n));
    }
}
 
// This Code is Contributed by vt_m.>

PHP

<?php
// PHP Program to find
// sum of square of first
// n natural numbers.
// This program avoids
// overflow upto some
// extent for large value
// of n.
 
// Return the sum of square
// of first n natural numbers
function squaresum($n)
{
    return ($n * ($n + 1) / 2) *
           (2 * $n + 1) / 3;
}
 
    // Driver Code
    $n = 4;
    echo squaresum($n) ;
     
// This code is contributed by vt_m.
?>

Javascript

<script>
 
// javascript Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
 
// Return the sum of square of first n natural
// numbers
function squaresum( n)
{
    return (n * (n + 1) / 2) * (2 * n + 1) / 3;
}
 
// Driven Program
 
    let n = 4;
     document.write(squaresum(n));
 
// This code contributed by aashish1995
 
</script>

Producción: 

30

Complejidad temporal: O(1) desde que se realizan operaciones constantes

Complejidad del espacio : O(1) ya que usa variables constantes

Publicación traducida automáticamente

Artículo escrito por anuj0503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *