Dado un número entero N , la tarea es calcular la suma de los primeros N números naturales sumando todas las potencias de 2 dos veces a la suma.
Ejemplos:
Entrada: N = 4
Salida: 17
Explicación:
Suma = 2 + 4 +3+ 8 = 17
Dado que 1, 2 y 4 son 2 0 , 2 1 y 2 2 respectivamente, se suman dos veces a la suma.
Entrada: N = 5
Salida: 22
Explicación:
La suma es igual a 2 + 4 +3+ 8 +5 = 22,
porque 1, 2 y 4 son 2 0 , 2 1 y 2 2 respectivamente.
Enfoque ingenuo:
el enfoque más simple para resolver este problema es iterar hasta N y seguir calculando la suma sumando todos los números una vez, excepto las potencias de 2 , que deben sumarse dos veces.
Complejidad de tiempo: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
Siga los pasos a continuación para optimizar el enfoque anterior:
- Calcula la suma de los primeros N números naturales mediante la fórmula (N * (N + 1)) / 2 .
- Ahora, todas las potencias de 2 deben agregarse una vez más. La suma de todas las potencias de 2 hasta N se puede calcular como 2 log 2 (N) + 1 – 1 .
- Por lo tanto, la suma requerida es:
(N * (N + 1)) / 2 + 2 log 2 (N) + 1 – 1
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 raise N to the
// power P and return the value
double power(int N, int P)
{
return pow(N, P);
}
// Function to calculate the
// log base 2 of an integer
int Log2(int N)
{
// Calculate log2(N) indirectly
// using log() method
int result = (int)(log(N) / log(2));
return result;
}
// Function to calculate and
// return the required sum
double specialSum(int n)
{
// Sum of first N natural
// numbers
double sum = n * (n + 1) / 2;
// Sum of all powers of 2
// up to N
int a = Log2(n);
sum = sum + power(2, a + 1) - 1;
return sum;
}
// Driver code
int main()
{
int n = 4;
cout << (specialSum(n)) << endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.Math;
class GFG {
// Function to raise N to the
// power P and return the value
static double power(int N, int P)
{
return Math.pow(N, P);
}
// Function to calculate the
// log base 2 of an integer
public static int log2(int N)
{
// Calculate log2(N) indirectly
// using log() method
int result = (int)(Math.log(N)
/ Math.log(2));
return result;
}
// Function to calculate and
// return the required sum
static double specialSum(int n)
{
// Sum of first N natural
// numbers
double sum = n * (n + 1) / 2;
// Sum of all powers of 2
// up to N
int a = log2(n);
sum = sum + power(2, a + 1) - 1;
return sum;
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
System.out.println(specialSum(n));
}
}
Python3
# Python3 program to implement # the above approach import math # Function to raise N to the # power P and return the value def power(N, P): return math.pow(N, P) # Function to calculate the # log base 2 of an integer def Log2(N): # Calculate log2(N) indirectly # using log() method result = (math.log(N) // math.log(2)) return result # Function to calculate and # return the required sum def specialSum(n): # Sum of first N natural # numbers sum = n * (n + 1) // 2 # Sum of all powers of 2 # up to N a = Log2(n) sum = sum + power(2, a + 1) - 1 return sum # Driver code if __name__=="__main__": n = 4 print(specialSum(n)) # This code is contributed by rutvik_56
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to raise N to the
// power P and return the value
static double power(int N, int P)
{
return Math.Pow(N, P);
}
// Function to calculate the
// log base 2 of an integer
public static int log2(int N)
{
// Calculate log2(N) indirectly
// using log() method
int result = (int)(Math.Log(N) /
Math.Log(2));
return result;
}
// Function to calculate and
// return the required sum
static double specialSum(int n)
{
// Sum of first N natural
// numbers
double sum = (double)(n) * (n + 1) / 2;
// Sum of all powers of 2
// up to N
int a = log2(n);
sum = (sum) + power(2, a + 1) - 1;
return sum;
}
// Driver Code
public static void Main(string[] args)
{
int n = 4;
Console.Write(specialSum(n));
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to raise N to the
// power P and return the value
function power(N, P)
{
return Math.pow(N, P);
}
// Function to calculate the
// log base 2 of an integer
function Log2(N)
{
// Calculate log2(N) indirectly
// using log() method
let result = (Math.floor(Math.log(N) / Math.log(2)));
return result;
}
// Function to calculate and
// return the required sum
function specialSum(n)
{
// Sum of first N natural
// numbers
let sum = n * (n + 1) / 2;
// Sum of all powers of 2
// up to N
let a = Log2(n);
sum = sum + power(2, a + 1) - 1;
return sum;
}
// Driver Code
let n = 4;
document.write(specialSum(n) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Producción:
17.0
Complejidad de Tiempo: O(log 2 (N))
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.