Dado un entero positivo n . La tarea es encontrar la suma de la suma de los cuadrados del primer n número natural.
Ejemplos:
Input : n = 3 Output : 20 Sum of square of first natural number = 1 Sum of square of first two natural number = 1^2 + 2^2 = 5 Sum of square of first three natural number = 1^2 + 2^2 + 3^2 = 14 Sum of sum of square of first three natural number = 1 + 5 + 14 = 20 Input : n = 2 Output : 6
Método 1: O(n) La idea es encontrar la suma de los cuadrados del primer i número natural, donde 1 <= i <= n. Y los suman todos.
Podemos encontrar la suma de los cuadrados de los primeros n números naturales mediante la fórmula: n * (n + 1)* (2*n + 1)/6
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find the sum of sum of
// squares of first n natural number
#include <bits/stdc++.h>
using namespace std;
// Function to find sum of sum of square of
// first n natural number
int findSum(int n)
{
int sum = 0;
for (int i = 1; i <= n; i++)
sum += ((i * (i + 1) * (2 * i + 1)) / 6);
return sum;
}
// Driven Program
int main()
{
int n = 3;
cout << findSum(n) << endl;
return 0;
}
Java
// Java Program to find the sum of
// sum of squares of first n natural
// number
class GFG {
// Function to find sum of sum of
// square of first n natural number
static int findSum(int n)
{
int sum = 0;
for (int i = 1; i <= n; i++)
sum += ((i * (i + 1)
* (2 * i + 1)) / 6);
return sum;
}
// Driver Program
public static void main(String[] args)
{
int n = 3;
System.out.println( findSum(n));
}
}
// This code is contributed by
// Arnab Kundu
Python3
# Python3 Program to find the sum # of sum of squares of first n # natural number # Function to find sum of sum of # square of first n natural number def findSum(n): summ = 0 for i in range(1, n+1): summ = (summ + ((i * (i + 1) * (2 * i + 1)) / 6)) return summ # Driven Program n = 3 print(int(findSum(n))) # This code is contributed by # Prasad Kshirsagar
C#
// C# Program to find the sum of sum of
// squares of first n natural number
using System;
public class GFG {
// Function to find sum of sum of
// square of first n natural number
static int findSum(int n)
{
int sum = 0;
for (int i = 1; i <= n; i++)
sum += ((i * (i + 1) *
(2 * i + 1)) / 6);
return sum;
}
// Driver Program
static public void Main()
{
int n = 3;
Console.WriteLine(findSum(n));
}
}
// This code is contributed by
// Arnab Kundu.
PHP
<?php
// PHP Program to find the sum of
// squares of first n natural number
// Function to find sum of sum of
// square of first n natural number
function findSum( $n)
{
$sum = 0;
for ($i = 1; $i <= $n; $i++)
$sum += (($i * ($i + 1) *
(2 * $i + 1)) / 6);
return $sum;
}
// Driver Code
$n = 3;
echo findSum($n) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Program to find the sum of sum of
// squares of first n natural number
// Function to find sum of sum of square
// of first n natural number
function findSum(n)
{
return (n * (n + 1) * (n + 1) * (n + 2)) / 12;
}
// Driven Program
let n = 3;
document.write(findSum(n) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Producción :
20
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Método 2: O(1)
Matemáticamente, necesitamos encontrar, Σ ((i * (i + 1) * (2*i + 1)/6), donde 1 <= i <= n
Entonces, resolvamos esta suma,
Sum = Σ ((i * (i + 1) * (2*i + 1)/6), where 1 <= i <= n
= (1/6)*(Σ ((i * (i + 1) * (2*i + 1)))
= (1/6)*(Σ ((i2 + i) * (2*i + 1))
= (1/6)*(Σ ((2*i3 + 3*i2 + i))
= (1/6)*(Σ 2*i3 + Σ 3*i2 + Σ i)
= (1/6)*(2*Σ i3 + 3*Σ i2 + Σ i)
= (1/6)*(2*(i*(i + 1)/2)2 + 3*(i * (i + 1) * (2*i + 1))/6 + i * (i + 1)/2)
= (1/6)*(i * (i + 1))((i*(i + 1)/2) + ((2*i + 1)/2) + 1/2)
= (1/12) * (i * (i + 1)) * ((i*(i + 1)) + (2*i + 1) + 1)
= (1/12) * (i * (i + 1)) * ((i2 + 3 * i + 2)
= (1/12) * (i * (i + 1)) * ((i + 1) * (i + 2))
= (1/12) * (i * (i + 1)2 * (i + 2))
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find the sum of sum of
// squares of first n natural number
#include <bits/stdc++.h>
using namespace std;
// Function to find sum of sum of square
// of first n natural number
int findSum(int n)
{
return (n * (n + 1) * (n + 1) * (n + 2)) / 12;
}
// Driven Program
int main()
{
int n = 3;
cout << findSum(n) << endl;
return 0;
}
Java
// Java Program to find the sum of sum of
// squares of first n natural number
class GFG {
// Function to find sum of sum of
// square of first n natural number
static int findSum(int n)
{
return (n * (n + 1) *
(n + 1) * (n + 2)) / 12;
}
// Driver Program
public static void main(String[] args)
{
int n = 3;
System.out.println(findSum(n) );
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 Program to find the sum # of sum of squares of first n # natural number # Function to find sum of sum of # square of first n natural number def findSum(n): return ((n * (n + 1) * (n + 1) * (n + 2)) / 12) # Driven Program n = 3 print(int(findSum(n))) # This code is contributed by # Prasad Kshirsagar
C#
// C# Program to find the sum of sum of
// squares of first n natural number
using System;
class GFG {
// Function to find sum of sum of
// square of first n natural number
static int findSum(int n)
{
return (n * (n + 1) * (n + 1)
* (n + 2)) / 12;
}
// Driver Program
static public void Main()
{
int n = 3;
Console.WriteLine(findSum(n) );
}
}
// This code is contributed by Arnab Kundu
PHP
<?php
// PHP Program to find the sum of sum of
// squares of first n natural number
// Function to find sum of sum of square
// of first n natural number
function findSum($n)
{
return ($n * ($n + 1) *
($n + 1) * ($n +
2)) / 12;
}
// Driver Code
$n = 3;
echo findSum($n) ;
// This code is contributed by nitin mittal
?>
Javascript
<script>
// js Program to find the sum of sum of
// squares of first n natural number
// Function to find sum of sum of square
// of first n natural number
function findSum($n)
{
return (n * (n + 1) *(n + 1) * (n + 2)) / 12;
}
// Driver Code
n = 3;
document.write(findSum(n)) ;
// This code is contributed by sravan kumar
</script>
Producción:
20
Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)