Dado un número N (tal vez hasta 10^9). La tarea es encontrar la suma de los primeros N números naturales tomando potencias de 2 como un número negativo.
Ejemplos:
Input: N = 4 Output: -4 - 1 - 2 + 3 - 4 = -4 1, 2, and 4 are the powers of two. Input: N = 5 Output: 1
Enfoque: una solución eficiente es almacenar las potencias de dos en una array y luego almacenar la presunción de esta array en otra array. Este tamaño de array puede ser como máximo 30. Por lo tanto, normalmente busque el primer elemento en la array de potencia que sea mayor que el número dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// to store power of 2
int power[31];
// to store presum of the power of 2's
int pre[31];
// function to find power of 2
void PowerOfTwo()
{
// to store power of 2
int x = 1;
for (int i = 0; i < 31; i++) {
power[i] = x;
x *= 2;
}
// to store pre sum
pre[0] = 1;
for (int i = 1; i < 31; i++)
pre[i] = pre[i - 1] + power[i];
}
// Function to find the sum
int Sum(int n)
{
// first store sum of
// first n natural numbers.
int ans = n * (n + 1) / 2;
// find the first greater number than given
// number then minus double of this
// from answer
for (int i = 0; i < 31; i++) {
if (power[i] > n) {
ans -= 2 * pre[i - 1];
break;
}
}
return ans;
}
// Driver code
int main()
{
// function call
PowerOfTwo();
int n = 4;
// function call
cout << Sum(n);
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
// to store power of 2
int power[31];
// to store presum of the power of 2's
int pre[31];
// function to find power of 2
void PowerOfTwo()
{
// to store power of 2
int x = 1;
for (int i = 0; i < 31; i++) {
power[i] = x;
x *= 2;
}
// to store pre sum
pre[0] = 1;
for (int i = 1; i < 31; i++)
pre[i] = pre[i - 1] + power[i];
}
// Function to find the sum
int Sum(int n)
{
// first store sum of
// first n natural numbers.
int ans = n * (n + 1) / 2;
// find the first greater number than given
// number then minus double of this
// from answer
for (int i = 0; i < 31; i++) {
if (power[i] > n) {
ans -= 2 * pre[i - 1];
break;
}
}
return ans;
}
// Driver code
int main()
{
// function call
PowerOfTwo();
int n = 4;
// function call
printf("%d",Sum(n));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java implementation of above approach
import java.io.*;
class GFG {
// to store power of 2
static int power[] = new int[31];
// to store presum of the power of 2's
static int pre[] = new int[31];
// function to find power of 2
static void PowerOfTwo()
{
// to store power of 2
int x = 1;
for (int i = 0; i < 31; i++) {
power[i] = x;
x *= 2;
}
// to store pre sum
pre[0] = 1;
for (int i = 1; i < 31; i++)
pre[i] = pre[i - 1] + power[i];
}
// Function to find the sum
static int Sum(int n)
{
// first store sum of
// first n natural numbers.
int ans = n * (n + 1) / 2;
// find the first greater number than given
// number then minus double of this
// from answer
for (int i = 0; i < 31; i++) {
if (power[i] > n) {
ans -= 2 * pre[i - 1];
break;
}
}
return ans;
}
// Driver code
public static void main (String[] args) {
// function call
PowerOfTwo();
int n = 4;
// function call
System.out.println( Sum(n));
}
}
// This code is contributed by ajit
Python 3
# Python 3 implementation of # above approach # to store power of 2 power = [0] * 31 # to store presum of the # power of 2's pre = [0] * 31 # function to find power of 2 def PowerOfTwo(): # to store power of 2 x = 1 for i in range(31): power[i] = x x *= 2 # to store pre sum pre[0] = 1 for i in range(1, 31): pre[i] = pre[i - 1] + power[i] # Function to find the sum def Sum(n): # first store sum of # first n natural numbers. ans = n * (n + 1) // 2 # find the first greater number # than given number then minus # double of this from answer for i in range( 31) : if (power[i] > n): ans -= 2 * pre[i - 1] break return ans # Driver code if __name__ == "__main__": # function call PowerOfTwo() n = 4 # function call print(Sum(n)) # This code is contributed # by ChitraNayal
C#
// C# implementation of
// above approach
using System;
class GFG
{
// to store power of 2
static int[] power = new int[31];
// to store presum of the
// power of 2's
static int[] pre = new int[31];
// function to find power of 2
static void PowerOfTwo()
{
// to store power of 2
int x = 1;
for (int i = 0; i < 31; i++)
{
power[i] = x;
x *= 2;
}
// to store pre sum
pre[0] = 1;
for (int i = 1; i < 31; i++)
pre[i] = pre[i - 1] + power[i];
}
// Function to find the sum
static int Sum(int n)
{
// first store sum of
// first n natural numbers.
int ans = n * (n + 1) / 2;
// find the first greater number
// than given number then minus
// double of this from answer
for (int i = 0; i < 31; i++)
{
if (power[i] > n)
{
ans -= 2 * pre[i - 1];
break;
}
}
return ans;
}
// Driver code
public static void Main ()
{
// function call
PowerOfTwo();
int n = 4;
// function call
Console.WriteLine(Sum(n));
}
}
// This code is contributed
// by anuj_67
PHP
<?php
// PHP implementation of above approach
// to store power of 2
$power = array_fill(0, 31, 0);
// to store presum of the
// power of 2's
$pre = array_fill(0, 31, 0);
// function to find power of 2
function PowerOfTwo()
{
global $power, $pre;
// to store power of 2
$x = 1;
for ($i = 0; $i < 31; $i++)
{
$power[$i] = $x;
$x *= 2;
}
// to store pre sum
$pre[0] = 1;
for ($i = 1; $i < 31; $i++)
$pre[$i] = $pre[$i - 1] + $power[$i];
}
// Function to find the sum
function Sum($n)
{
global $power, $pre;
// first store sum of
// first n natural numbers.
$ans = $n * ($n + 1) / 2;
// find the first greater number
// than given number then minus
// double of this from answer
for ($i = 0; $i < 31; $i++)
if ($power[$i] > $n)
{
$ans -= 2 * $pre[$i - 1];
break;
}
return $ans;
}
// Driver code
// function call
PowerOfTwo();
$n = 4;
// function call
print(Sum($n));
// This code is contributed by mits
?>
Javascript
<script>
// javascript implementation of above approach
// to store power of 2
power = Array(31).fill(0);
// to store presum of the power of 2's
pre = Array(31).fill(0);
// function to find power of 2
function PowerOfTwo()
{
// to store power of 2
var x = 1;
for (i = 0; i < 31; i++)
{
power[i] = x;
x *= 2;
}
// to store pre sum
pre[0] = 1;
for (i = 1; i < 31; i++)
pre[i] = pre[i - 1] + power[i];
}
// Function to find the sum
function Sum(n)
{
// first store sum of
// first n natural numbers.
var ans = n * (n + 1) / 2;
// find the first greater number than given
// number then minus var of this
// from answer
for (i = 0; i < 31; i++)
{
if (power[i] > n)
{
ans -= 2 * pre[i - 1];
break;
}
}
return ans;
}
// Driver code
// function call
PowerOfTwo();
var n = 4;
// function call
document.write( Sum(n));
// This code is contributed by shikhasingrajput
</script>
Producción:
-4
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA