Sum of first N natural numbers when N is extremely large
Given a positive integer n, the task is to find the sum of the first n natural numbers given that n is very large (1 ? n ? 1020000).
Examples:
Input: n = 4
Output: 10 1 + 2 + 3 + 4 = 10Input: n = 12345678910
Output: 76207893880582233505
Approach: Sum of first n natural numbers is (n * (n + 1)) / 2 but given that n can be extremely large (1 ? n ? 1020000). Now its obvious that we can only store the sum in a string. A simple solution is to run a loop till n and calculate the sum by the method of addition of two strings and iteratively add all numbers one by one but time complexity of this solution will be very large. We can optimise this solution using BigInteger class in java. BigInteger class gives pre-defined methods for Mathematical operations which can be used to solve (n * (n + 1)) / 2 to calculate the required result.
- Take a string for holding the value of extremely large input.
- Transform this string to a BigInteger.
- Calculate (n * (n + 1)) / 2 using BigInteger class’s pre-defined methods.
- Print the calculated sum in the end.
Below is the implementation of the above approach:
C++14
// C++ program to find the sum of the first n // natural numbers when n is very large #include<bits/stdc++.h> using namespace std; string divide(string number, int divisor) { // As result can be very large store it in string string ans; // Find prefix of number that is larger // than divisor. int idx = 0; int temp = number[idx] - '0' ; while (temp < divisor) temp = temp * 10 + (number[++idx] - '0' ); // Repeatedly divide divisor with temp. After // every division, update temp to include one // more digit. while (number.size() > idx) { // Store result in answer i.e. temp / divisor ans += (temp / divisor) + '0' ; // Take next digit of number temp = (temp % divisor) * 10 + number[++idx] - '0' ; } // If divisor is greater than number if (ans.length() == 0) return "0" ; // else return ans return ans; } string multiply(string num1, string num2) { int len1 = num1.size(); int len2 = num2.size(); if (len1 == 0 || len2 == 0) return "0" ; // will keep the result number in vector // in reverse order vector< int > result(len1 + len2, 0); // Below two indexes are used to find positions // in result. int i_n1 = 0; int i_n2 = 0; // Go from right to left in num1 for ( int i=len1-1; i>=0; i--) { int carry = 0; int n1 = num1[i] - '0' ; // To shift position to left after every // multiplication of a digit in num2 i_n2 = 0; // Go from right to left in num2 for ( int j=len2-1; j>=0; j--) { // Take current digit of second number int n2 = num2[j] - '0' ; // Multiply with current digit of first number // and add result to previously stored result // at current position. int sum = n1*n2 + result[i_n1 + i_n2] + carry; // Carry for next iteration carry = sum/10; // Store result result[i_n1 + i_n2] = sum % 10; i_n2++; } // store carry in next cell if (carry > 0) result[i_n1 + i_n2] += carry; // To shift position to left after every // multiplication of a digit in num1. i_n1++; } // ignore '0's from the right int i = result.size() - 1; while (i>=0 && result[i] == 0) i--; // If all were '0's - means either both or // one of num1 or num2 were '0' if (i == -1) return "0" ; // generate the result string string s = "" ; while (i >= 0) s += std::to_string(result[i--]); return s; } // Function to return the sum of first n natural numbers string Sum(string n) { string y=to_string(stol(n)+1); string res=multiply(n,y); string ans=divide(res,2); //string result = multiply(x,y); return ans; } // Driver code int main() { string n = "12345678910" ; cout<<Sum(n); } |
Java
// Java program to find the sum of the first n // natural numbers when n is very large import java.math.BigInteger; class w3wiki { // Function to return the sum of first // n natural numbers static BigInteger sum(String n) { // b1 = 1 BigInteger b1 = BigInteger.ONE; // b2 = 2 BigInteger b2 = new BigInteger( "2" ); // Converting n to BigInteger BigInteger bigInt = new BigInteger(n); // Calculating (n * (n + 1)) / 2 BigInteger result = (bigInt.multiply(bigInt.add(b1))).divide(b2); return result; } // Driver code public static void main(String[] args) throws java.lang.Exception { String n = "12345678910" ; System.out.println(sum(n)); } } |
Python3
# Python3 program to find the sum # of first n natural numbers when # n is very large # Function to return the sum of # first n natural numbers def Sum (n): result = (n * (n + 1 )) / / 2 return result # Driver Code if __name__ = = "__main__" : n = "12345678910" print ( Sum ( int (n))) # This code is contributed # by Rituraj_Jain |
PHP
<?php // PHP program to find the sum // of first n natural numbers when // n is very large // Function to return the sum of // first n natural numbers function Sum( $n ) { $result = ( $n * (int)(( $n + 1)) / 2); return $result ; } // Driver Code $n = "12345678910" ; echo Sum( $n ); // This code is contributed // by Akanksha Rai ?> |
Javascript
// Javascript program to find the sum of the first n // natural numbers when n is very large // Function to return the sum of first n natural numbers function Sum(n) { let result = (Number(n)*(Number(n)+1))/2; return result; } // Driver code let n = "12345678910" ; console.log(Sum(n)); // This code is contributed by Ishan Khandelwal |
76207893880582233505
Time Complexity: O(1), This algorithm runs in the constant time since the time required to calculate the sum of the first n natural numbers is independent of the value of n.
Auxiliary Space: O(1), This algorithm requires a constant amount of space since the only data structure used is a BigInteger.
Contact Us