Sum of first N natural numbers by taking powers of 2 as negative number

0 0 6 minutes read

Given a number N ( maybe up to 10^9 ). The task is to find the sum of first N natural number taking powers of 2 as a negative number.
Examples:

Input: N = 4
Output: -4
- 1 - 2 + 3 - 4 = -4
1, 2, and 4 are the powers of two.

Input: N = 5
Output: 1

Approach: An efficient solution is to store the powers of two in an array and then store presum of this array in another array. This array size can be at most 30. So, normally search for the first element in the power array which is greater than the given number.
Below is the implementation of above approach:

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>

Output:

-4

Time Complexity: O(31)

Auxiliary Space: O(31)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!