# Calculate sum of all integers from 1 to N, excluding perfect power of 2

• Last Updated : 05 Nov, 2021

Given a positive integer N, the task is to calculate the sum of all integers from 1 to N but excluding the number which is a perfect power of 2.
Examples:

Input: N = 2
Output: 0
Input: N = 1000000000
Output: 499999998352516354

Naive Approach:
The naive approach is to iterate every number from 1 to N and compute the sum in the variable by excluding the number which is a perfect power of 2. But to compute the sum to the number 10^9, the above approach will give Time Limit Error.
Time Complexity: O(N)
Efficient Approach:
To find desired sum, below are the steps:

1. Find the sum of all the number till N using the formula discussed in this article in O(1) time.
2. Since sum of all perfect power of 2 forms a Geometric Progression. Hence the sum of all powers of 2 less than N is calculated by the below formula:

The number of element with perfect power of 2 less than N is given by log2N
Let r = log2
And the sum of all numbers which are perfect power of 2 is given by 2r – 1

1.
2. Subtract the sum of all perfect powers of 2 calculated above from the sum of first N numbers to get the result.

Below is the implementation of the above approach:

## C++

 `// C++ implementation of the``// approach``#include ``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

 ``

Output:

`0`

Time Complexity: O(1)

Auxiliary Space: O(1)

My Personal Notes arrow_drop_up
{"ft_lang_label":"__label__en","ft_lang_prob":0.72373456,"math_prob":0.9862784,"size":4144,"snap":"2022-27-2022-33","text_gpt3_token_len":1274,"char_repetition_ratio":0.1589372,"word_repetition_ratio":0.3647199,"special_character_ratio":0.32890928,"punctuation_ratio":0.096370466,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999943,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-07-06T23:39:45Z\",\"WARC-Record-ID\":\"<urn:uuid:74f0e63a-d7e0-4d65-8c62-9d390e86a546>\",\"Content-Length\":\"158358\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:167f3cbe-ab24-4efc-8510-3a9f266f4d90>\",\"WARC-Concurrent-To\":\"<urn:uuid:4591e00a-2d2b-4c9b-9f2c-3d34699a5a55>\",\"WARC-IP-Address\":\"23.45.233.19\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/calculate-sum-of-all-integers-from-1-to-n-excluding-perfect-power-of-2/\",\"WARC-Payload-Digest\":\"sha1:VIDPVVLHPYHIM6JSXEAJK7BSUHJZGC2A\",\"WARC-Block-Digest\":\"sha1:WFSPHQZOMUIGTVDPIKSTKMZFRAPLQ3GO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656104678225.97_warc_CC-MAIN-20220706212428-20220707002428-00281.warc.gz\"}"}