Dados dos números como strings. Los números pueden ser muy grandes (pueden no caber en long long int), la tarea es encontrar la suma de estos dos números.
Ejemplos:
Input : str1 = "3333311111111111",
str2 = "44422222221111"
Output : 3377733333332222
Input : str1 = "7777555511111111",
str2 = "3332222221111"
Output : 7780887733332222
La idea se basa en las matemáticas escolares. Atravesamos ambas strings desde el final, una por una agregamos dígitos y realizamos un seguimiento del acarreo. Para simplificar el proceso, hacemos lo siguiente:
1) Invertir ambas strings.
2) Continúe agregando dígitos uno por uno desde el índice 0 (en strings invertidas) hasta el final de la string más pequeña, agregue la suma % 10 al final del resultado y realice un seguimiento del acarreo como suma/10.
3) Finalmente invertir el resultado.
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
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
?>
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>
Producción:
198123
Complejidad de tiempo: O(n1+n2) donde n1 y n2 son longitudes de dos strings de entrada que representan números.
Espacio auxiliar: O(max(n1, n2))
Optimización:
podemos evitar las dos primeras operaciones inversas de strings atravesándolas desde el final. A continuación se muestra la solución optimizada.
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();
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);
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();
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 = ((int)(str1.charAt(i)-'0') +
(int)(str2.charAt(i+diff)-'0') + carry);
str += (char)(sum % 10 + '0');
carry = sum / 10;
}
// Add remaining digits of str2[]
for (int i = n2 - n1 - 1; i >= 0; 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
return new StringBuilder(str).reverse().toString();
}
// 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
# python 3 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):
temp = str1
str1 = str2
str2 = temp
# Take an empty string for storing result
str3 = ""
# Calculate length of both string
n1 = len(str1)
n2 = len(str2)
diff = n2 - n1
# Initially take carry zero
carry = 0
# Traverse from end of both strings
for i in range(n1-1,-1,-1):
# Do school mathematics, compute sum of
# current digits and carry
sum = ((ord(str1[i])-ord('0')) +
int((ord(str2[i+diff])-ord('0'))) + carry)
str3 = str3+str(sum%10 )
carry = sum//10
# Add remaining digits of str2[]
for i in range(n2-n1-1,-1,-1):
sum = ((ord(str2[i])-ord('0'))+carry)
str3 = str3+str(sum%10 )
carry = sum//10
# Add remaining carry
if (carry):
str3+str(carry+'0')
# reverse resultant string
str3 = str3[::-1]
return str3
# Driver code
if __name__ == "__main__":
str1 = "12"
str2 = "198111"
print(findSum(str1, str2))
# This code is contributed by ChitraNayal
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;
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 = ((int)(str1[i] - '0') +
(int)(str2[i + diff]-'0') + carry);
str += (char)(sum % 10 + '0');
carry = sum / 10;
}
// Add remaining digits of str2[]
for (int i = n2 - n1 - 1; i >= 0; 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);
return new string(ch2);
}
// Driver code
static void Main()
{
string str1 = "12";
string str2 = "198111";
Console.WriteLine(findSum(str1, str2));
}
}
// This code is contributed by mits
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))
{
$temp = $str1;
$str1 = $str2;
$str2 = $temp;
}
// Take an empty string for storing result
$str3 = "";
// Calculate length of both string
$n1 = strlen($str1);
$n2 = strlen($str2);
$diff = $n2 - $n1;
// Initially take carry zero
$carry = 0;
// Traverse from end of both strings
for ($i = $n1 - 1; $i >= 0; $i--)
{
// Do school mathematics, compute sum
// of current digits and carry
$sum = ((ord($str1[$i]) - ord('0')) +
((ord($str2[$i + $diff]) -
ord('0'))) + $carry);
$str3 .= chr($sum % 10 + ord('0'));
$carry = (int)($sum / 10);
}
// Add remaining digits of str2[]
for ($i = $n2 - $n1 - 1; $i >= 0; $i--)
{
$sum = ((ord($str2[$i]) - ord('0')) + $carry);
$str3 .= chr($sum % 10 + ord('0'));
$carry = (int)($sum / 10);
}
// Add remaining carry
if ($carry)
$str3 .= chr($carry + ord('0'));
// reverse resultant string
return strrev($str3);
}
// Driver code
$str1 = "12";
$str2 = "198111";
print(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 temp = str1
str1 = str2
str2 = temp
}
// Take an empty string for storing result
let str = "";
// Calculate length of both string
let n1 = str1.length, n2 = str2.length;
let diff = n2 - n1;
// Initially take carry zero
let carry = 0;
// Traverse from end of both strings
for (let i=n1-1; i>=0; i--)
{
// Do school mathematics, compute sum of
// current digits and carry
// console.log((str1.charCodeAt(i)-48),(str2.charCodeAt(i+diff)-48))
let sum = ((str1.charCodeAt(i)-48) +
(str2.charCodeAt(i+diff)-48) +
carry);
str+=(sum%10);
carry = Math.floor(sum/10);
}
// // Add remaining digits of str2[]
for (let i=n2-n1-1; i>=0; i--)
{
let sum = ((str2.charCodeAt(i)-48)+carry);
str+=(sum%10);
carry = Math.floor(sum/10);
}
// Add remaining carry
if (carry)
str+=(carry+'0');
// reverse resultant string
str = str.split("").reverse().join("");
return str;
}
// Driver code
let str1 = "12";
let str2 = "198111";
document.write(findSum(str1, str2),"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción:
198123
Complejidad de tiempo: O(max(n1, n2)) donde n1 y n2 son longitudes de dos strings de entrada que representan números.
Espacio auxiliar: O(max(n1, n2))
Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA