Sum of first N natural numbers by taking powers of 2 as negative number
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)
Contact Us