Suma de los primeros n números impares en O(1) Complejidad

Dada la secuencia de números impares 
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23,…. 
Encuentra la suma de los primeros n números impares
Ejemplos: 
 

Input : n = 2
Output : 4
Sum of first two odd numbers is 1 + 3 = 4.

Input : 5
Output : 25
Sum of first 5 odd numbers is 1 + 3 + 5 +
7 + 9 = 25

Una solución simple es iterar a través de todos los números impares. 
 

C++

// A naive CPP program to find sum of
// first n odd numbers
#include <iostream>
using namespace std;
 
// Returns the sum of first
// n odd numbers
int oddSum(int n)
{
    int sum = 0, curr = 1;
    for (int i = 0; i < n; i++) {
        sum += curr;
        curr += 2;
    }
    return sum;
}
 
// Driver function
int main()
{
    int n = 20;
    cout << " Sum of first " << n
         << " Odd Numbers is: " << oddSum(n);
    return 0;
}

Java

// Java program to find sum of
// first n odd numbers
import java.util.*;
 
class Odd
{  
    // Returns the sum of first
    // n odd numbers
    public static int oddSum(int n)
    {
        int sum = 0, curr = 1;
        for (int i = 0; i < n; i++) {
            sum += curr;
            curr += 2;
        }
        return sum;
    }
     
    // driver function
    public static void main(String[] args)
    {
        int n = 20;
        System.out.println(" Sum of first "+ n
        +" Odd Numbers is: "+oddSum(n));
    }
}
 
// This code is contributed by rishabh_jain

Python3

# Python3 program to find sum
# of first n odd numbers
 
def oddSum(n) :
    sum = 0
    curr = 1
    i = 0
    while i < n:
        sum = sum + curr
        curr = curr + 2
        i = i + 1
    return sum
 
# Driver Code
n = 20
print (" Sum of first" , n, "Odd Numbers is: ",
                                oddSum(n) )
 
# This code is contributed by rishabh_jain

C#

// C# program to find sum of
// first n odd numbers
using System;
 
class GFG {
     
    // Returns the sum of first
    // n odd numbers
    public static int oddSum(int n)
    {
        int sum = 0, curr = 1;
        for (int i = 0; i < n; i++) {
            sum += curr;
            curr += 2;
        }
         
        return sum;
    }
 
    // driver function
    public static void Main()
    {
        int n = 20;
        Console.WriteLine(" Sum of first " + n
            + " Odd Numbers is: " + oddSum(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// A naive PHP program to find sum of
// first n odd numbers
 
// Returns the sum of first
// n odd numbers
function oddSum($n)
{
    $sum = 0; $curr = 1;
    for ($i = 0; $i < $n; $i++)
    {
        $sum += $curr;
        $curr += 2;
    }
    return $sum;
}
 
// Driver Code
$n = 20;
echo " Sum of first ", $n
     , " Odd Numbers is: ", oddSum($n);
      
// This code is contributed by vt_m.
?>

Javascript

<script>
 
// A naive Javascript program to find sum of
// first n odd numbers
 
// Returns the sum of first
// n odd numbers
function oddSum(n)
{
    let sum = 0; curr = 1;
    for (let i = 0; i < n; i++)
    {
        sum += curr;
        curr += 2;
    }
    return sum;
}
 
// Driver Code
let n = 20;
document.write(" Sum of first " + n
     + " Odd Numbers is: " + oddSum(n));
      
// This code is contributed by gfgking.
</script>

Producción: 

Sum of first 20 odd numbers is 400

Complejidad de Tiempo: O(n) 
Espacio Auxiliar: O(1)
 
Una solución eficiente es usar la fórmula directa. Para encontrar la suma de los primeros n números impares, podemos aplicar el teorema de los números impares, establece que la suma de los primeros n números impares es igual al cuadrado de n.
 

∑(2i – 1) = n 2 donde i varía de 1 a n

Sea n = 10, por lo tanto, la suma de los 10 primeros números impares es
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100
si aplicamos el teorema de los números impares:
suma de los 10 primeros números impares = n * n = 10 * 10 = 100.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// Efficient program to find sum of
// first n odd numbers
#include <iostream>
using namespace std;
 
// Returns the sum of first
// n odd numbers
int oddSum(int n)
{
    return (n * n);
}
 
// Driver function
int main()
{
    int n = 20;
    cout << " Sum of first " << n
         << " Odd Numbers is: " << oddSum(n);
    return 0;
}

Java

// Java program to find sum of
// first n odd numbers
import java.util.*;
 
class Odd
{  
    // Returns the sum of first
    // n odd numbers
    public static int oddSum(int n)
    {
        return (n * n);
    }
     
    // driver function
    public static void main(String[] args)
    {
        int n = 20;
        System.out.println(" Sum of first "+ n
        +" Odd Numbers is: "+oddSum(n));
    }
}
 
// This code is contributed by rishabh_jain

Python3

# Python3 program to find sum
# of first n odd numbers
 
def oddSum(n) :
    return (n * n);
 
# Driver Code
n = 20
print (" Sum of first" , n, "Odd Numbers is: ",
                               oddSum(n) )
 
# This code is contributed by rishabh_jain

C#

// C# program to find sum of
// first n odd numbers
using System;
 
class GFG {
     
    // Returns the sum of first
    // n odd numbers
    public static int oddSum(int n)
    {
        return (n * n);
    }
 
    // driver function
    public static void Main()
    {
        int n = 20;
        Console.WriteLine(" Sum of first " + n
            + " Odd Numbers is: " + oddSum(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// Efficient program to find sum of
// first n odd numbers
 
// Returns the sum of first
// n odd numbers
function oddSum($n)
{
    return ($n * $n);
}
 
// Driver Code
$n = 20;
echo " Sum of first " , $n,
     " Odd Numbers is: ", oddSum($n);
 
// This code is contributed by vt_m.
?>

Javascript

<script>
    // Javascript program to find sum of first n odd numbers
     
    // Returns the sum of first
    // n odd numbers
    function oddSum(n)
    {
        return (n * n);
    }
     
    let n = 20;
    document.write(" Sum of first " + n
                      + " Odd Numbers is: " + oddSum(n));
     
    // This code is contributed by divyesh072019.
</script>

Producción: 
 

Sum of first 20 odd numbers is 400

Complejidad Temporal: O(1) 
Espacio Auxiliar : O(1)
¿Cómo funciona?  
Podemos demostrarlo usando inducción matemática. Sabemos que es cierto para n = 1 y n = 2 ya que las sumas son 1 y 4 (1 + 3) respectivamente.
 

Let it be true for n = k-1.

Sum of first k odd numbers = 
  Sum of first k-1 odd numbers + k'th odd number
= (k-1)*(k-1) + (2k - 1)
= k*k

Publicación traducida automáticamente

Artículo escrito por ARSHPREET_SINGH 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 *