Dada una serie de números 1, 2, 4, 3, 5, 7, 9, 6, 8, 10, 11, 13… La tarea es encontrar la suma de todos los números en serie hasta el N-ésimo número.
Ejemplos:
Entrada: N = 4
Salida: 10
1 + 2 + 4 + 3 = 10
Entrada: N = 10
Salida: 55
Enfoque : La serie es básicamente 2 0 números impares, 2 1 números pares, 2 2 números pares…. La suma de los primeros N números impares es N * N y la suma de los primeros N números pares es (N * (N+1)) . Calcule la suma de 2 i números pares o impares y siga sumándolos a la suma.
Iterar por cada potencia de 2, hasta que el número de iteraciones exceda N, y seguir sumando la respectiva sumatoria de números pares o impares según la paridad. Para cada segmento, la suma del segmento será (suma actual de X números pares/impares – suma anterior de Y números pares/impares), donde X es la suma total de los números pares/impares hasta este segmento e Y es la suma de los números pares/impares hasta el anterior cuando se produjeron los números pares/impares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// sum of first N odd numbers
int sumodd(int n)
{
return (n * n);
}
// Function to find the
// sum of first N even numbers
int sumeven(int n)
{
return (n * (n + 1));
}
// Function to overall
// find the sum of series
int findSum(int num)
{
// Initial odd numbers
int sumo = 0;
// Initial even numbers
int sume = 0;
// First power of 2
int x = 1;
// Check for parity
// for odd/even
int cur = 0;
// Counts the sum
int ans = 0;
while (num > 0) {
// Get the minimum
// out of remaining num
// or power of 2
int inc = min(x, num);
// Decrease that much numbers
// from num
num -= inc;
// If the segment has odd numbers
if (cur == 0) {
// Summate the odd numbers
// By exclusion
ans = ans + sumodd(sumo + inc) - sumodd(sumo);
// Increase number of odd numbers
sumo += inc;
}
// If the segment has even numbers
else {
// Summate the even numbers
// By exclusion
ans = ans + sumeven(sume + inc) - sumeven(sume);
// Increase number of even numbers
sume += inc;
}
// Next set of numbers
x *= 2;
// Change parity for odd/even
cur ^= 1;
}
return ans;
}
// Driver code
int main()
{
int n = 4;
cout << findSum(n);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG
{
// Function to find the
// sum of first N odd numbers
static int sumodd(int n)
{
return (n * n);
}
// Function to find the
// sum of first N even numbers
static int sumeven(int n)
{
return (n * (n + 1));
}
// Function to overall
// find the sum of series
static int findSum(int num)
{
// Initial odd numbers
int sumo = 0;
// Initial even numbers
int sume = 0;
// First power of 2
int x = 1;
// Check for parity
// for odd/even
int cur = 0;
// Counts the sum
int ans = 0;
while (num > 0)
{
// Get the minimum
// out of remaining num
// or power of 2
int inc = Math.min(x, num);
// Decrease that much numbers
// from num
num -= inc;
// If the segment has odd numbers
if (cur == 0)
{
// Summate the odd numbers
// By exclusion
ans = ans + sumodd(sumo + inc) - sumodd(sumo);
// Increase number of odd numbers
sumo += inc;
}
// If the segment has even numbers
else
{
// Summate the even numbers
// By exclusion
ans = ans + sumeven(sume + inc) - sumeven(sume);
// Increase number of even numbers
sume += inc;
}
// Next set of numbers
x *= 2;
// Change parity for odd/even
cur ^= 1;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 4;
System.out.println(findSum(n));
}
}
// This code contributed by Rajput-Ji
Python
# Python3 program to implement # the above approach # Function to find the # sum of first N odd numbers def sumodd(n): return (n * n) # Function to find the # sum of first N even numbers def sumeven(n): return (n * (n + 1)) # Function to overall # find the sum of series def findSum(num): # Initial odd numbers sumo = 0 # Initial even numbers sume = 0 # First power of 2 x = 1 # Check for parity # for odd/even cur = 0 # Counts the sum ans = 0 while (num > 0): # Get the minimum # out of remaining num # or power of 2 inc = min(x, num) # Decrease that much numbers # from num num -= inc # If the segment has odd numbers if (cur == 0): # Summate the odd numbers # By exclusion ans = ans + sumodd(sumo + inc) - sumodd(sumo) # Increase number of odd numbers sumo += inc # If the segment has even numbers else: # Summate the even numbers # By exclusion ans = ans + sumeven(sume + inc) - sumeven(sume) # Increase number of even numbers sume += inc # Next set of numbers x *= 2 # Change parity for odd/even cur ^= 1 return ans # Driver code n = 4 print(findSum(n)) # This code is contributed by mohit kumar
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the
// sum of first N odd numbers
static int sumodd(int n)
{
return (n * n);
}
// Function to find the
// sum of first N even numbers
static int sumeven(int n)
{
return (n * (n + 1));
}
// Function to overall
// find the sum of series
static int findSum(int num)
{
// Initial odd numbers
int sumo = 0;
// Initial even numbers
int sume = 0;
// First power of 2
int x = 1;
// Check for parity
// for odd/even
int cur = 0;
// Counts the sum
int ans = 0;
while (num > 0)
{
// Get the minimum
// out of remaining num
// or power of 2
int inc = Math.Min(x, num);
// Decrease that much numbers
// from num
num -= inc;
// If the segment has odd numbers
if (cur == 0)
{
// Summate the odd numbers
// By exclusion
ans = ans + sumodd(sumo + inc) - sumodd(sumo);
// Increase number of odd numbers
sumo += inc;
}
// If the segment has even numbers
else
{
// Summate the even numbers
// By exclusion
ans = ans + sumeven(sume + inc) - sumeven(sume);
// Increase number of even numbers
sume += inc;
}
// Next set of numbers
x *= 2;
// Change parity for odd/even
cur ^= 1;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int n = 4;
Console.WriteLine(findSum(n));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP program to implement
// the above approach
// Function to find the
// sum of first N odd numbers
function sumodd($n)
{
return ($n * $n);
}
// Function to find the
// sum of first N even numbers
function sumeven($n)
{
return ($n * ($n + 1));
}
// Function to overall
// find the sum of series
function findSum( $num)
{
// Initial odd numbers
$sumo = 0;
// Initial even numbers
$sume = 0;
// First power of 2
$x = 1;
// Check for parity
// for odd/even
$cur = 0;
// Counts the sum
$ans = 0;
while ($num > 0)
{
// Get the minimum
// out of remaining num
// or power of 2
$inc = min($x, $num);
// Decrease that much numbers
// from num
$num -= $inc;
// If the segment has odd numbers
if ($cur == 0)
{
// Summate the odd numbers
// By exclusion
$ans = $ans + sumodd($sumo + $inc) -
sumodd($sumo);
// Increase number of odd numbers
$sumo += $inc;
}
// If the segment has even numbers
else
{
// Summate the even numbers
// By exclusion
$ans = $ans + sumeven($sume + $inc) -
sumeven($sume);
// Increase number of even numbers
$sume += $inc;
}
// Next set of numbers
$x *= 2;
// Change parity for odd/even
$cur ^= 1;
}
return $ans;
}
// Driver code
$n = 4;
echo findSum($n);
// This code contributed by princiraj1992
?>
Javascript
<script>
// javascript program to implement
// the above approach
// Function to find the
// sum of first N odd numbers
function sumodd( n)
{
return (n * n);
}
// Function to find the
// sum of first N even numbers
function sumeven( n)
{
return (n * (n + 1));
}
// Function to overall
// find the sum of series
function findSum( num)
{
// Initial odd numbers
let sumo = 0;
// Initial even numbers
let sume = 0;
// First power of 2
let x = 1;
// Check for parity
// for odd/even
let cur = 0;
// Counts the sum
let ans = 0;
while (num > 0) {
// Get the minimum
// out of remaining num
// or power of 2
let inc = Math.min(x, num);
// Decrease that much numbers
// from num
num -= inc;
// If the segment has odd numbers
if (cur == 0) {
// Summate the odd numbers
// By exclusion
ans = ans + sumodd(sumo + inc) - sumodd(sumo);
// Increase number of odd numbers
sumo += inc;
}
// If the segment has even numbers
else {
// Summate the even numbers
// By exclusion
ans = ans + sumeven(sume + inc) - sumeven(sume);
// Increase number of even numbers
sume += inc;
}
// Next set of numbers
x *= 2;
// Change parity for odd/even
cur ^= 1;
}
return ans;
}
// Driver code
let n = 4;
document.write( findSum(n));
// This code is contributed by todaysgaurav
</script>
Producción:
10
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)