Calcule la suma de todos los números enteros de 1 a N, excluyendo la potencia perfecta de 2

Dado un entero positivo N , la tarea es calcular la suma de todos los enteros del 1 al N pero excluyendo el número que es una potencia perfecta de 2.
Ejemplos: 
 

Entrada: N = 2 
Salida: 0
Entrada: N = 1000000000 
Salida: 499999998352516354 
 

Enfoque ingenuo: 
el enfoque ingenuo es iterar cada número de 1 a N y calcular la suma en la variable excluyendo el número que es una potencia perfecta de 2. Pero para calcular la suma del número 10^9 , el enfoque anterior será dar error de límite de tiempo .
Complejidad de tiempo: O (N)
Enfoque eficiente: 
Para encontrar la suma deseada, a continuación se detallan los pasos: 
 

1. Encuentre la suma de todos los números hasta N usando la fórmula discutida en este artículo en tiempo O (1) .
2. Ya que la suma de todas las potencias perfectas de 2 forma una Progresión Geométrica. Por lo tanto, la suma de todas las potencias de 2 menores que N se calcula mediante la siguiente fórmula: 
    

El número de elementos con potencia perfecta de 2 menor que N está dado por log ₂ N , 
Sea r = log ₂ N 
Y la suma de todos los números que son potencia perfecta de 2 está dada por 2 ^r – 1 . 
 

1.  
2. Resta la suma de todas las potencias perfectas de 2 calculadas anteriormente de la suma de los primeros N números para obtener el resultado.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the
// approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required
// summation
void findSum(int N)
{
    // Find the sum of first N
    // integers using the formula
    int sum = (N) * (N + 1) / 2;
     
    int r = log2(N) + 1;
     
    // Find the sum of numbers
    // which are exact power of
    // 2 by using the formula
    int expSum = pow(2, r) - 1;   
 
    // Print the final Sum
    cout << sum - expSum << endl;
}
 
// Driver's Code
int main()
{
    int N = 2;
 
    // Function to find the
    // sum
    findSum(N);
    return 0;
}

// Java implementation of the above approach
import java.lang.Math;
 
class GFG{
     
// Function to find the required
// summation
public static void findSum(int N)
{
 
    // Find the sum of first N
    // integers using the formula
    int sum = (N) * (N + 1) / 2;
         
    int r = (int)(Math.log(N) /
                  Math.log(2)) + 1;
         
    // Find the sum of numbers
    // which are exact power of
    // 2 by using the formula
    int expSum = (int)(Math.pow(2, r)) - 1;    
     
    // Print the final Sum
    System.out.println(sum - expSum);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2;
 
    // Function to find the sum
    findSum(N);
}
}
 
// This code is contributed by divyeshrabadiya07

# Python 3 implementation of the
# approach
from math import log2,pow
 
# Function to find the required
# summation
def findSum(N):
    # Find the sum of first N
    # integers using the formula
    sum = (N) * (N + 1) // 2
     
    r = log2(N) + 1
     
    # Find the sum of numbers
    # which are exact power of
    # 2 by using the formula
    expSum = pow(2, r) - 1
 
    # Print the final Sum
    print(int(sum - expSum))
 
# Driver's Code
if __name__ == '__main__':
    N = 2
 
    # Function to find the
    # sum
    findSum(N)
     
# This code is contributed by Surendra_Gangwar

// C# implementation of the above approach
using System;
 
class GFG{
     
// Function to find the required
// summation
public static void findSum(int N)
{
 
    // Find the sum of first N
    // integers using the formula
    int sum = (N) * (N + 1) / 2;
         
    int r = (int)(Math.Log(N) /
                  Math.Log(2)) + 1;
         
    // Find the sum of numbers
    // which are exact power of
    // 2 by using the formula
    int expSum = (int)(Math.Pow(2, r)) - 1;
     
    // Print the final Sum
    Console.Write(sum - expSum);
}
 
// Driver Code
public static void Main(string[] args)
{
    int N = 2;
 
    // Function to find the sum
    findSum(N);
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript implementation of the above approach
 
// Function to find the required
// summation
function findSum(N)
{
     
    // Find the sum of first N
    // integers using the formula
    var sum = (N) * (N + 1) / 2;
         
    var r = (Math.log(N) /
             Math.log(2)) + 1;
         
    // Find the sum of numbers
    // which are exact power of
    // 2 by using the formula
    var expSum = (Math.pow(2, r)) - 1;    
     
    // Print the final Sum
    document.write(sum - expSum);
}
     
// Driver code
var N = 2;
 
// Function to find the sum
findSum(N);
 
// This code is contributed by Kirti
 
</script>

0

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)