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:
- Encuentre la suma de todos los números hasta N usando la fórmula discutida en este artículo en tiempo O (1) .
- 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 2 N ,
Sea r = log 2 N
Y la suma de todos los números que son potencia perfecta de 2 está dada por 2 r – 1 .
- 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++
// 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
// 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
Python3
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA