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 2int power[31];// to store presum of the power of 2'sint pre[31];// function to find power of 2void 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 sumint 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 codeint 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 2int power[31];// to store presum of the power of 2'sint pre[31];// function to find power of 2void 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 sumint 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 codeint 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 approachimport java.io.*;class GFG { // to store power of 2static int power[] = new int[31];// to store presum of the power of 2'sstatic int pre[] = new int[31];// function to find power of 2static 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 sumstatic 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 2power = [0] * 31# to store presum of the # power of 2'spre = [0] * 31# function to find power of 2def 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 sumdef 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 codeif __name__ == "__main__": # function call PowerOfTwo() n = 4 # function call print(Sum(n))# This code is contributed # by ChitraNayal |
C#
// C# implementation of // above approachusing System;class GFG { // to store power of 2static int[] power = new int[31];// to store presum of the // power of 2'sstatic int[] pre = new int[31];// function to find power of 2static 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 sumstatic 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 codepublic 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 2function 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 sumfunction 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 callPowerOfTwo();$n = 4;// function callprint(Sum($n));// This code is contributed by mits?> |
Javascript
<script>// javascript implementation of above approach // to store power of 2power = Array(31).fill(0);// to store presum of the power of 2'spre = Array(31).fill(0);// function to find power of 2function 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 sumfunction 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 callPowerOfTwo();var n = 4;// function calldocument.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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
