Sum of two large numbers
Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers.
Examples:
Input : str1 = "3333311111111111",
str2 = "44422222221111"
Output : 3377733333332222
Input : str1 = "7777555511111111",
str2 = "3332222221111"
Output : 7780887733332222
Approach 1: Using BigInteger class
The simplest approach is use BigInteger class. BigInteger provides analogues to all of Java’s primitive integer operators, and all relevant methods from java.lang.Math. In this approach we will create 2 objects of BigInteger and pass string in it then add simply add those objects using add() method.
C++
#include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <cstdlib> #include <cstring> #include <ctime> #include <functional> #include <iomanip> #include <iostream> #include <numeric> #include <sstream> #include <string> #include <vector> using namespace std; // Define a struct to represent BigInteger struct BigInteger { string str; // Constructor to initialize // BigInteger with a string BigInteger(string s) { str = s; } // Overload + operator to add // two BigInteger objects BigInteger operator+( const BigInteger& b) { string a = str; string c = b.str; int alen = a.length(), clen = c.length(); int n = max(alen, clen); if (alen > clen) c.insert(0, alen - clen, '0' ); else if (alen < clen) a.insert(0, clen - alen, '0' ); string res(n + 1, '0' ); int carry = 0; for ( int i = n - 1; i >= 0; i--) { int digit = (a[i] - '0' ) + (c[i] - '0' ) + carry; carry = digit / 10; res[i + 1] = digit % 10 + '0' ; } if (carry == 1) { res[0] = '1' ; return BigInteger(res); } else { return BigInteger(res.substr(1)); } } // Overload << operator to output // BigInteger object friend ostream& operator<<(ostream& out, const BigInteger& b) { out << b.str; return out; } }; // Driver Code int main() { string str = "7777555511111111" ; string str1 = "3332222221111" ; // Create BigInteger objects // and add them BigInteger a(str); BigInteger b(str1); BigInteger sum = a + b; // Output the result cout << sum << endl; return 0; } |
Java
import java.util.*; import java.math.*; public class GFG{ public static void main(String []args){ String str= "7777555511111111" ; String str1= "3332222221111" ; BigInteger a= new BigInteger(str); // creating obj of biginteger and pass str in it BigInteger b= new BigInteger(str1); // creating obj of biginteger and pass str1 in it System.out.println(a.add(b)); //add } } |
Python3
# Define the input strings str = "7777555511111111" str1 = "3332222221111" # Create int objects with arbitrary precision a = int ( str ) b = int (str1) # Add the int objects result = a + b # Print the result print (result) |
C#
// C# code addition using System; using System.Collections.Generic; // Implementing biginteger class. public class BigInteger { private List< int > digits; // Constructor public BigInteger( string value) { digits = new List< int >(); for ( int i = value.Length - 1; i >= 0; i--) { digits.Add( int .Parse(value[i].ToString())); } } // Add function in BigInteger. public static BigInteger Add(BigInteger a, BigInteger b) { List< int > sum = new List< int >(); int carry = 0; int i = 0; while (i < a.digits.Count || i < b.digits.Count) { int x = i < a.digits.Count ? a.digits[i] : 0; int y = i < b.digits.Count ? b.digits[i] : 0; int s = x + y + carry; sum.Add(s % 10); carry = s / 10; i++; } if (carry > 0) { sum.Add(carry); } BigInteger result = new BigInteger( "" ); for ( int j = sum.Count - 1; j >= 0; j--) { result.digits.Add(sum[j]); } return result; } // An override function to convert them to string. public override string ToString() { string result = "" ; foreach ( int digit in digits) { result += digit.ToString(); } return result; } } public class GFG { public static void Main() { string str = "7777555511111111" ; string str1 = "3332222221111" ; BigInteger a = new BigInteger(str); // convert the string to a BigInteger BigInteger b = new BigInteger(str1); // convert the string to a BigInteger Console.WriteLine(BigInteger.Add(a, b)); // add the two BigIntegers and print the result } } // The code is contributed by Nidhi goel. |
Javascript
// Define the input strings let str = "7777555511111111" ; let str1 = "3332222221111" ; // Create BigInt objects with arbitrary precision let a = BigInt(str); let b = BigInt(str1); // Add the BigInt objects let result = a + b; // Print the result console.log(result.toString()); |
7780887733332222
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach 2: Iterative approach
The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following:
1) Reverse both strings.
2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10.
3) Finally reverse the result.
C++
// C++ program to find sum of two large numbers. #include<bits/stdc++.h> using namespace std; // Function for finding sum of larger numbers string findSum(string str1, string str2) { // Before proceeding further, make sure length // of str2 is larger. if (str1.length() > str2.length()) swap(str1, str2); // Take an empty string for storing result string str = "" ; // Calculate length of both string int n1 = str1.length(), n2 = str2.length(); // Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; for ( int i=0; i<n1; i++) { // Do school mathematics, compute sum of // current digits and carry int sum = ((str1[i]- '0' )+(str2[i]- '0' )+carry); str.push_back(sum%10 + '0' ); // Calculate carry for next step carry = sum/10; } // Add remaining digits of larger number for ( int i=n1; i<n2; i++) { int sum = ((str2[i]- '0' )+carry); str.push_back(sum%10 + '0' ); carry = sum/10; } // Add remaining carry if (carry) str.push_back(carry+ '0' ); // reverse resultant string reverse(str.begin(), str.end()); return str; } // Driver code int main() { string str1 = "12" ; string str2 = "198111" ; cout << findSum(str1, str2); return 0; } |
Java
// Java program to find sum of two large numbers. import java.util.*; class GFG { // Function for finding sum of larger numbers static String findSum(String str1, String str2) { // Before proceeding further, make sure length // of str2 is larger. if (str1.length() > str2.length()){ String t = str1; str1 = str2; str2 = t; } // Take an empty String for storing result String str = "" ; // Calculate length of both String int n1 = str1.length(), n2 = str2.length(); // Reverse both of Strings str1= new StringBuilder(str1).reverse().toString(); str2= new StringBuilder(str2).reverse().toString(); int carry = 0 ; for ( int i = 0 ; i < n1; i++) { // Do school mathematics, compute sum of // current digits and carry int sum = (( int )(str1.charAt(i) - '0' ) + ( int )(str2.charAt(i) - '0' ) + carry); str += ( char )(sum % 10 + '0' ); // Calculate carry for next step carry = sum / 10 ; } // Add remaining digits of larger number for ( int i = n1; i < n2; i++) { int sum = (( int )(str2.charAt(i) - '0' ) + carry); str += ( char )(sum % 10 + '0' ); carry = sum / 10 ; } // Add remaining carry if (carry > 0 ) str += ( char )(carry + '0' ); // reverse resultant String str = new StringBuilder(str).reverse().toString(); return str; } // Driver code public static void main(String[] args) { String str1 = "12" ; String str2 = "198111" ; System.out.println(findSum(str1, str2)); } } // This code is contributed by mits |
Python3
# Python3 program to find sum of # two large numbers. # Function for finding sum of # larger numbers def findSum(str1, str2): # Before proceeding further, # make sure length of str2 is larger. if ( len (str1) > len (str2)): t = str1; str1 = str2; str2 = t; # Take an empty string for # storing result str = ""; # Calculate length of both string n1 = len (str1); n2 = len (str2); # Reverse both of strings str1 = str1[:: - 1 ]; str2 = str2[:: - 1 ]; carry = 0 ; for i in range (n1): # Do school mathematics, compute # sum of current digits and carry sum = (( ord (str1[i]) - 48 ) + (( ord (str2[i]) - 48 ) + carry)); str + = chr ( sum % 10 + 48 ); # Calculate carry for next step carry = int ( sum / 10 ); # Add remaining digits of larger number for i in range (n1, n2): sum = (( ord (str2[i]) - 48 ) + carry); str + = chr ( sum % 10 + 48 ); carry = ( int )( sum / 10 ); # Add remaining carry if (carry): str + = chr (carry + 48 ); # reverse resultant string str = str [:: - 1 ]; return str ; # Driver code str1 = "12" ; str2 = "198111" ; print (findSum(str1, str2)); # This code is contributed by mits |
C#
// C# program to find sum of two large numbers. using System; class GFG { // Function for finding sum of larger numbers static string findSum( string str1, string str2) { // Before proceeding further, make sure length // of str2 is larger. if (str1.Length > str2.Length){ string t = str1; str1 = str2; str2 = t; } // Take an empty string for storing result string str = "" ; // Calculate length of both string int n1 = str1.Length, n2 = str2.Length; // Reverse both of strings char [] ch = str1.ToCharArray(); Array.Reverse( ch ); str1 = new string ( ch ); char [] ch1 = str2.ToCharArray(); Array.Reverse( ch1 ); str2 = new string ( ch1 ); int carry = 0; for ( int i = 0; i < n1; i++) { // Do school mathematics, compute sum of // current digits and carry int sum = (( int )(str1[i] - '0' ) + ( int )(str2[i] - '0' ) + carry); str += ( char )(sum % 10 + '0' ); // Calculate carry for next step carry = sum/10; } // Add remaining digits of larger number for ( int i = n1; i < n2; i++) { int sum = (( int )(str2[i] - '0' ) + carry); str += ( char )(sum % 10 + '0' ); carry = sum/10; } // Add remaining carry if (carry > 0) str += ( char )(carry + '0' ); // reverse resultant string char [] ch2 = str.ToCharArray(); Array.Reverse( ch2 ); str = new string ( ch2 ); return str; } // Driver code static void Main() { string str1 = "12" ; string str2 = "198111" ; Console.WriteLine(findSum(str1, str2)); } } // This code is contributed by mits |
Javascript
<script> // Javascript program to find sum of // two large numbers. // Function for finding sum of larger numbers function findSum(str1, str2) { // Before proceeding further, make // sure length of str2 is larger. if (str1.length > str2.length) { let t = str1; str1 = str2; str2 = t; } // Take an empty String for storing result let str = "" ; // Calculate length of both String let n1 = str1.length, n2 = str2.length; // Reverse both of Strings str1 = str1.split( "" ).reverse().join( "" ); str2 = str2.split( "" ).reverse().join( "" ); let carry = 0; for (let i = 0; i < n1; i++) { // Do school mathematics, compute sum of // current digits and carry let sum = ((str1[i].charCodeAt(0) - '0' .charCodeAt(0)) + (str2[i].charCodeAt(0) - '0' .charCodeAt(0)) + carry); str += String.fromCharCode(sum % 10 + '0' .charCodeAt(0)); // Calculate carry for next step carry = Math.floor(sum / 10); } // Add remaining digits of larger number for (let i = n1; i < n2; i++) { let sum = ((str2[i].charCodeAt(0) - '0' .charCodeAt(0)) + carry); str += String.fromCharCode(sum % 10 + '0' .charCodeAt(0)); carry = Math.floor(sum / 10); } // Add remaining carry if (carry > 0) str += String.fromCharCode(carry + '0' .charCodeAt(0)); // reverse resultant String str = str.split( "" ).reverse().join( "" ); return str; } // Driver code let str1 = "12" ; let str2 = "198111" ; document.write(findSum(str1, str2)) // This code is contributed by rag2127 </script> |
PHP
<?php // PHP program to find sum of two large numbers. // Function for finding sum of larger numbers function findSum( $str1 , $str2 ) { // Before proceeding further, make sure length // of str2 is larger. if ( strlen ( $str1 ) > strlen ( $str2 )) { $t = $str1 ; $str1 = $str2 ; $str2 = $t ; } // Take an empty string for storing result $str = "" ; // Calculate length of both string $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); // Reverse both of strings $str1 = strrev ( $str1 ); $str2 = strrev ( $str2 ); $carry = 0; for ( $i =0; $i < $n1 ; $i ++) { // Do school mathematics, compute sum of // current digits and carry $sum = ((ord( $str1 [ $i ])-48)+((ord( $str2 [ $i ])-48)+ $carry )); $str .= chr ( $sum %10 + 48); // Calculate carry for next step $carry = (int)( $sum /10); } // Add remaining digits of larger number for ( $i = $n1 ; $i < $n2 ; $i ++) { $sum = ((ord( $str2 [ $i ])-48)+ $carry ); $str .= chr ( $sum %10 + 48); $carry = (int)( $sum /10); } // Add remaining carry if ( $carry ) $str .= chr ( $carry +48); // reverse resultant string $str = strrev ( $str ); return $str ; } // Driver code $str1 = "12" ; $str2 = "198111" ; echo findSum( $str1 , $str2 ); // This code is contributed by mits ?> |
Output:
198123
Time Complexity: O(n1+n2) where n1 and n2 are lengths of two input strings representing numbers.
Auxiliary Space: O(max(n1, n2))
Approach 3 : Optimization
We can avoid the first two string reverse operations by traversing them from the end. Below is the optimized solution.
C++
#include<bits/stdc++.h> using namespace std; // Function for finding sum of larger numbers string findSum(string str1, string str2) { // Remove leading zeros from both strings str1.erase(0, min(str1.find_first_not_of( '0' ), str1.size()-1)); str2.erase(0, min(str2.find_first_not_of( '0' ), str2.size()-1)); // If both strings become empty, return "0" if (str1.empty() && str2.empty()) return "0" ; // Before proceeding further, make sure length // of str2 is larger. if (str1.length() > str2.length()) swap(str1, str2); // Take an empty string for storing result string str = "" ; // Calculate length of both string int n1 = str1.length(), n2 = str2.length(); int diff = n2 - n1; // Initially take carry zero int carry = 0; // Traverse from end of both strings for ( int i=n1-1; i>=0; i--) { // Do school mathematics, compute sum of // current digits and carry int sum = ((str1[i]- '0' ) + (str2[i+diff]- '0' ) + carry); str.push_back(sum%10 + '0' ); carry = sum/10; } // Add remaining digits of str2[] for ( int i=n2-n1-1; i>=0; i--) { int sum = ((str2[i]- '0' )+carry); str.push_back(sum%10 + '0' ); carry = sum/10; } // Add remaining carry if (carry) str.push_back(carry+ '0' ); // reverse resultant string reverse(str.begin(), str.end()); return str; } // Driver code int main() { string str1 = "12" ; string str2 = "198111" ; cout << findSum(str1, str2); // Output: 0 return 0; } |
Java
import java.util.*; public class Main { // Function for finding sum of larger numbers static String findSum(String str1, String str2) { str1 = str1.replaceFirst( "^0+(?!$)" , "" ); str2 = str2.replaceFirst( "^0+(?!$)" , "" ); if (str1.isEmpty() && str2.isEmpty()) return "0" ; if (str1.length() > str2.length()) { String temp = str1; str1 = str2; str2 = temp; } StringBuilder str = new StringBuilder(); int n1 = str1.length(), n2 = str2.length(); int diff = n2 - n1; int carry = 0 ; for ( int i = n1 - 1 ; i >= 0 ; i--) { int sum = ((str1.charAt(i) - '0' ) + (str2.charAt(i + diff) - '0' ) + carry); str.append(( char ) (sum % 10 + '0' )); carry = sum / 10 ; } for ( int i = n2 - n1 - 1 ; i >= 0 ; i--) { int sum = ((str2.charAt(i) - '0' ) + carry); str.append(( char ) (sum % 10 + '0' )); carry = sum / 10 ; } if (carry != 0 ) str.append(( char ) (carry + '0' )); return str.reverse().toString(); } // Driver code public static void main(String[] args) { String str1 = "12" ; String str2 = "198111" ; System.out.println(findSum(str1, str2)); // Output: 0 } } |
Python3
def find_sum(str1, str2): str1 = str1.lstrip( '0' ) str2 = str2.lstrip( '0' ) if not str1 and not str2: return '0' if len (str1) > len (str2): str1, str2 = str2, str1 result = [] n1, n2 = len (str1), len (str2) diff = n2 - n1 carry = 0 for i in range (n1 - 1 , - 1 , - 1 ): _sum = int (str1[i]) + int (str2[i + diff]) + carry result.append( str (_sum % 10 )) carry = _sum / / 10 for i in range (n2 - n1 - 1 , - 1 , - 1 ): _sum = int (str2[i]) + carry result.append( str (_sum % 10 )) carry = _sum / / 10 if carry: result.append( str (carry)) return ''.join(result[:: - 1 ]) # Driver code str1 = "12" str2 = "198111" print (find_sum(str1, str2)) # Output: 0 |
C#
using System; class Program { // Function for finding sum of larger numbers static string FindSum( string str1, string str2) { str1 = str1.TrimStart( '0' ); str2 = str2.TrimStart( '0' ); if ( string .IsNullOrEmpty(str1) && string .IsNullOrEmpty(str2)) return "0" ; if (str1.Length > str2.Length) { string temp = str1; str1 = str2; str2 = temp; } System.Text.StringBuilder result = new System.Text.StringBuilder(); int n1 = str1.Length, n2 = str2.Length; int diff = n2 - n1; int carry = 0; for ( int i = n1 - 1; i >= 0; i--) { int sum = ((str1[i] - '0' ) + (str2[i + diff] - '0' ) + carry); result.Append(( char )(sum % 10 + '0' )); carry = sum / 10; } for ( int i = n2 - n1 - 1; i >= 0; i--) { int sum = ((str2[i] - '0' ) + carry); result.Append(( char )(sum % 10 + '0' )); carry = sum / 10; } if (carry != 0) result.Append(( char )(carry + '0' )); char [] charArray = result.ToString().ToCharArray(); Array.Reverse(charArray); return new string (charArray); } // Driver code static void Main() { string str1 = "12" ; string str2 = "198111" ; Console.WriteLine(FindSum(str1, str2)); // Output: 0 } } |
Javascript
function findSum(str1, str2) { str1 = str1.replace(/^0+/, '' ); str2 = str2.replace(/^0+/, '' ); if (str1 === '' && str2 === '' ) { return '0' ; } if (str1.length > str2.length) { [str1, str2] = [str2, str1]; } let result = '' ; let n1 = str1.length; let n2 = str2.length; let diff = n2 - n1; let carry = 0; for (let i = n1 - 1; i >= 0; i--) { let sum = parseInt(str1[i]) + parseInt(str2[i + diff]) + carry; result += (sum % 10).toString(); carry = Math.floor(sum / 10); } for (let i = n2 - n1 - 1; i >= 0; i--) { let sum = parseInt(str2[i]) + carry; result += (sum % 10).toString(); carry = Math.floor(sum / 10); } if (carry !== 0) { result += carry.toString(); } return result.split( '' ).reverse().join( '' ); } // Driver code let str1 = "12" ; let str2 = "198111" ; console.log(findSum(str1, str2)); // Output: 0 |
PHP
<?php function findSum( $str1 , $str2 ) { $str1 = ltrim( $str1 , '0' ); $str2 = ltrim( $str2 , '0' ); if ( $str1 === '' && $str2 === '' ) { return '0' ; } if ( strlen ( $str1 ) > strlen ( $str2 )) { list( $str1 , $str2 ) = array ( $str2 , $str1 ); } $result = '' ; $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); $diff = $n2 - $n1 ; $carry = 0; for ( $i = $n1 - 1; $i >= 0; $i --) { $sum = (int) $str1 [ $i ] + (int) $str2 [ $i + $diff ] + $carry ; $result .= ( $sum % 10); $carry = (int)( $sum / 10); } for ( $i = $n2 - $n1 - 1; $i >= 0; $i --) { $sum = (int) $str2 [ $i ] + $carry ; $result .= ( $sum % 10); $carry = (int)( $sum / 10); } if ( $carry !== 0) { $result .= $carry ; } return strrev ( $result ); } // Driver code $str1 = "12" ; $str2 = "198111" ; echo findSum( $str1 , $str2 ); // Output: 0 ?> |
Output:
198123
Time Complexity: O(max(n1, n2)) where n1 and n2 are lengths of two input strings representing numbers.
Auxiliary Space: O(max(n1, n2))
Contact Us