Dados dos números positivos como strings. Los números pueden ser muy grandes (pueden no caber en int largo largo), la tarea es encontrar el producto de estos dos números.
Ejemplos:
Input : num1 = 4154
num2 = 51454
Output : 213739916
Input : num1 = 654154154151454545415415454
num2 = 63516561563156316545145146514654
Output : 41549622603955309777243716069997997007620439937711509062916
La idea se basa en las matemáticas escolares.
Partimos del último dígito del segundo número y lo multiplicamos por el primer número. Luego multiplicamos el segundo dígito del segundo número con el primer número, y así sucesivamente. Sumamos todas estas multiplicaciones. Mientras sumamos, ponemos la i-ésima multiplicación desplazada.
El enfoque utilizado en la siguiente solución es mantener solo una array para el resultado. Atravesamos todos los dígitos primero y segundo en un bucle y sumamos el resultado en la posición adecuada.
C++
// C++ program to multiply two numbers represented
// as strings.
#include<bits/stdc++.h>
using namespace std;
// Multiplies str1 and str2, and prints result.
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;
}
// Driver code
int main()
{
string str1 = "1235421415454545454545454544";
string str2 = "1714546546546545454544548544544545";
if((str1.at(0) == '-' || str2.at(0) == '-') &&
(str1.at(0) != '-' || str2.at(0) != '-' ))
cout<<"-";
if(str1.at(0) == '-')
str1 = str1.substr(1);
if(str2.at(0) == '-')
str2 = str2.substr(1);
cout << multiply(str1, str2);
return 0;
}
Java
// Java program to multiply two numbers
// represented as Strings.
class GFG
{
// Multiplies str1 and str2, and prints result.
static String multiply(String num1, String num2)
{
int len1 = num1.length();
int len2 = num2.length();
if (len1 == 0 || len2 == 0)
return "0";
// will keep the result number in vector
// in reverse order
int result[] = new int[len1 + len2];
// 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.charAt(i) - '0';
// To shift position to left after every
// multipliccharAtion 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.charAt(j) - '0';
// Multiply with current digit of first number
// and add result to previously stored result
// charAt current position.
int sum = n1 * n2 + result[i_n1 + i_n2] + carry;
// Carry for next itercharAtion
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
// multipliccharAtion of a digit in num1.
i_n1++;
}
// ignore '0's from the right
int i = result.length - 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";
// genercharAte the result String
String s = "";
while (i >= 0)
s += (result[i--]);
return s;
}
// Driver code
public static void main(String[] args)
{
String str1 = "1235421415454545454545454544";
String str2 = "1714546546546545454544548544544545";
if ((str1.charAt(0) == '-' || str2.charAt(0) == '-') &&
(str1.charAt(0) != '-' || str2.charAt(0) != '-'))
System.out.print("-");
if (str1.charAt(0) == '-')
str1 = str1.substring(1);
if (str2.charAt(0) == '-')
str2 = str2.substring(1);
System.out.println(multiply(str1, str2));
}
}
// This code is contributed by ankush_953
Python3
# Python3 program to multiply two numbers
# represented as strings.
# Multiplies str1 and str2, and prints result.
def multiply(num1, num2):
len1 = len(num1)
len2 = len(num2)
if len1 == 0 or len2 == 0:
return "0"
# will keep the result number in vector
# in reverse order
result = [0] * (len1 + len2)
# Below two indexes are used to
# find positions in result.
i_n1 = 0
i_n2 = 0
# Go from right to left in num1
for i in range(len1 - 1, -1, -1):
carry = 0
n1 = ord(num1[i]) - 48
# To shift position to left after every
# multiplication of a digit in num2
i_n2 = 0
# Go from right to left in num2
for j in range(len2 - 1, -1, -1):
# Take current digit of second number
n2 = ord(num2[j]) - 48
# Multiply with current digit of first number
# and add result to previously stored result
# at current position.
summ = n1 * n2 + result[i_n1 + i_n2] + carry
# Carry for next iteration
carry = summ // 10
# Store result
result[i_n1 + i_n2] = summ % 10
i_n2 += 1
# 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 += 1
# print(result)
# ignore '0's from the right
i = len(result) - 1
while (i >= 0 and result[i] == 0):
i -= 1
# 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
s = ""
while (i >= 0):
s += chr(result[i] + 48)
i -= 1
return s
# Driver code
str1 = "1235421415454545454545454544"
str2 = "1714546546546545454544548544544545"
if((str1[0] == '-' or str2[0] == '-') and
(str1[0] != '-' or str2[0] != '-')):
print("-", end = '')
if(str1[0] == '-' and str2[0] != '-'):
str1 = str1[1:]
elif(str1[0] != '-' and str2[0] == '-'):
str2 = str2[1:]
elif(str1[0] == '-' and str2[0] == '-'):
str1 = str1[1:]
str2 = str2[1:]
print(multiply(str1, str2))
# This code is contributed by ankush_953
C#
// C# program to multiply two numbers
// represented as Strings.
using System;
class GFG
{
// Multiplies str1 and str2, and prints result.
static String multiply(String num1, String num2)
{
int len1 = num1.Length;
int len2 = num2.Length;
if (len1 == 0 || len2 == 0)
return "0";
// will keep the result number in vector
// in reverse order
int []result = new int[len1 + len2];
// Below two indexes are used to
// find positions in result.
int i_n1 = 0;
int i_n2 = 0;
int i;
// Go from right to left in num1
for (i = len1 - 1; i >= 0; i--)
{
int carry = 0;
int n1 = num1[i] - '0';
// To shift position to left after every
// multipliccharAtion 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
// charAt current position.
int sum = n1 * n2 + result[i_n1 + i_n2] + carry;
// Carry for next itercharAtion
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
// multipliccharAtion of a digit in num1.
i_n1++;
}
// ignore '0's from the right
i = result.Length - 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";
// genercharAte the result String
String s = "";
while (i >= 0)
s += (result[i--]);
return s;
}
// Driver code
public static void Main(String[] args)
{
String str1 = "1235421415454545454545454544";
String str2 = "1714546546546545454544548544544545";
if ((str1[0] == '-' || str2[0] == '-') &&
(str1[0] != '-' || str2[0] != '-'))
Console.Write("-");
if (str1[0] == '-' && str2[0] != '-')
{
str1 = str1.Substring(1);
}
else if (str1[0] != '-' && str2[0] == '-')
{
str2 = str2.Substring(1);
}
else if (str1[0] == '-' && str2[0] == '-')
{
str1 = str1.Substring(1);
str2 = str2.Substring(1);
}
Console.WriteLine(multiply(str1, str2));
}
}
// This code is contributed by Rajput-Ji
Javascript
// JavaScript program to multiply two numbers
// represented as strings.
// Multiplies str1 and str2, and prints result.
function multiply(num1, num2)
{
let len1 = num1.length;
let len2 = num2.length;
if (len1 == 0 || len2 == 0)
return "0"
// will keep the result number in vector
// in reverse order
let result = new Array(len1 + len2).fill(0)
// Below two indexes are used to
// find positions in result.
let i_n1 = 0
let i_n2 = 0
// Go from right to left in num1
for (var i = len1 - 1; i > -1 ; i --)
{
let carry = 0
let n1 = (num1[i]).charCodeAt(0) - 48
// To shift position to left after every
// multiplication of a digit in num2
i_n2 = 0
// Go from right to left in num2
for (var j = len2 - 1; j > -1; j--)
{
// Take current digit of second number
let n2 = (num2[j]).charCodeAt(0) - 48
// Multiply with current digit of first number
// and add result to previously stored result
// at current position.
let summ = n1 * n2 + result[i_n1 + i_n2] + carry
// Carry for next iteration
carry = Math.floor(summ / 10)
// Store result
result[i_n1 + i_n2] = summ % 10
i_n2 += 1
}
// 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 += 1
// print(result)
}
// ignore '0's from the right
i = result.length - 1
while (i >= 0 && result[i] == 0)
i -= 1
// 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
let s = ""
while (i >= 0)
{
s += String.fromCharCode(result[i] + 48)
i -= 1
}
return s
}
// Driver code
let str1 = "1235421415454545454545454544"
let str2 = "1714546546546545454544548544544545"
if((str1[0] == '-' || str2[0] == '-') &&
(str1[0] != '-' || str2[0] != '-'))
process.stdout.write("-")
if(str1[0] == '-' && str2[0] != '-')
str1.shift()
else if(str1[0] != '-' && str2[0] == '-')
str2.shift()
else if(str1[0] == '-' && str2[0] == '-')
{
str1.shift()
str2.shift()
}
console.log(multiply(str1, str2))
// This code is contributed by phasing17
Producción:
2118187521397235888154583183918321221520083884298838480662480
El código anterior está adaptado del código proporcionado por Gaurav.
Complejidad de tiempo: O (m * n), donde m y n son la longitud de dos números que deben multiplicarse.
Espacio auxiliar: O(m+n), donde m y n son la longitud de dos números que deben multiplicarse.
Método 2:
C++
// Include header file
#include <bits/stdc++.h>
using namespace std;
int main()
{
string num1 = "1235421415454545454545454544";
string tempnum1 = num1;
string num2 = "1714546546546545454544548544544545";
string tempnum2 = num2;
// Check condition if one string is negative
if (num1[0] == '-' && num2[0] != '-') {
num1 = num1.substr(1);
}
else if (num1[0] != '-' && num2[0] == '-') {
num2 = num2.substr(1);
}
else if (num1[0] == '-' && num2[0] == '-') {
num1 = num1.substr(1);
num2 = num2.substr(1);
}
string s1 = num1;
string s2 = num2;
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
vector<int> m(s1.length() + s2.length());
// Go from right to left in num1
for (int i = 0; i < s1.length(); i++) {
// Go from right to left in num2
for (int j = 0; j < s2.length(); j++) {
m[i + j]
= m[i + j] + (s1[i] - '0') * (s2[j] - '0');
}
}
string product = "";
// Multiply with current digit of first number
// and add result to previously stored product
// at current position.
for (int i = 0; i < m.size(); i++) {
int digit = m[i] % 10;
int carry = m[i] / 10;
if (i + 1 < m.size()) {
m[i + 1] = m[i + 1] + carry;
}
product = to_string(digit) + product;
}
// ignore '0's from the right
while (product.length() > 1 && product[0] == '0') {
product = product.substr(1);
}
// Check condition if one string is negative
if (tempnum1[0] == '-' && tempnum2[0] != '-') {
product = "-" + product;
}
else if (tempnum1[0] != '-' && tempnum2[0] == '-') {
product = "-" + product;
}
cout << "Product of the two numbers is :"
<< "\n"
<< product << endl;
}
// This code is contributed by Aarti_Rathi
Java
// Java program to multiply two numbers represented
// as strings.
import java.util.Scanner;
public class StringMultiplication {
// Driver code
public static void main(String[] args)
{
String num1 = "1235421415454545454545454544";
String tempnum1 = num1;
String num2 = "1714546546546545454544548544544545";
String tempnum2 = num2;
// Check condition if one string is negative
if (num1.charAt(0) == '-'
&& num2.charAt(0) != '-') {
num1 = num1.substring(1);
}
else if (num1.charAt(0) != '-'
&& num2.charAt(0) == '-') {
num2 = num2.substring(1);
}
else if (num1.charAt(0) == '-'
&& num2.charAt(0) == '-') {
num1 = num1.substring(1);
num2 = num2.substring(1);
}
String s1
= new StringBuffer(num1).reverse().toString();
String s2
= new StringBuffer(num2).reverse().toString();
int[] m = new int[s1.length() + s2.length()];
// Go from right to left in num1
for (int i = 0; i < s1.length(); i++) {
// Go from right to left in num2
for (int j = 0; j < s2.length(); j++) {
m[i + j] = m[i + j]
+ (s1.charAt(i) - '0')
* (s2.charAt(j) - '0');
}
}
String product = new String();
// Multiply with current digit of first number
// and add result to previously stored product
// at current position.
for (int i = 0; i < m.length; i++) {
int digit = m[i] % 10;
int carry = m[i] / 10;
if (i + 1 < m.length) {
m[i + 1] = m[i + 1] + carry;
}
product = digit + product;
}
// ignore '0's from the right
while (product.length() > 1
&& product.charAt(0) == '0') {
product = product.substring(1);
}
// Check condition if one string is negative
if (tempnum1.charAt(0) == '-'
&& tempnum2.charAt(0) != '-') {
product = new StringBuffer(product)
.insert(0, '-')
.toString();
}
else if (tempnum1.charAt(0) != '-'
&& tempnum2.charAt(0) == '-') {
product = new StringBuffer(product)
.insert(0, '-')
.toString();
}
else if (tempnum1.charAt(0) == '-'
&& tempnum2.charAt(0) == '-') {
product = product;
}
System.out.println("Product of the two numbers is :"
+ "\n" + product);
}
}
Python3
# Python3 program to implement the above approach
# function to reverse the string
def reverse(s):
str = ""
for i in s:
str = i + str
return str
num1 = "1235421415454545454545454544"
tempnum1 = num1
num2 = "1714546546546545454544548544544545"
tempnum2 = num2
# Check condition if one string is negative
if (num1[0] == '-' and num2[0] != '-'):
num1 = num1[1:]
elif (num1[0] != '-' and num2[0] == '-'):
num2 = num2[1:]
elif (num1[0] == '-' and num2[0] == '-'):
num1 = num1[1:]
num2 = num2[1:]
s1 = num1
s2 = num2
s1 = reverse(s1)
s2 = reverse(s2)
m = [0]*(len(s1)+len(s2))
# Go from right to left in num1
for i in range(len(s1)):
# Go from right to left in num2
for j in range(len(s2)):
m[i + j] = m[i + j] + (ord(s1[i]) - 48) * (ord(s2[j]) - 48)
product = ""
# Multiply with current digit of first number
# and add result to previously stored product
# at current position.
for i in range(len(m)):
digit = m[i] % 10
carry = m[i] // 10
if (i + 1 < len(m)):
m[i + 1] = m[i + 1] + carry
product = str(digit) + product
# ignore '0's from the right
while (len(product) > 1 and product[0] == '0'):
product = product[1:]
#check condition if one string is negative
if (tempnum1[0] == '-' and tempnum2[0] != '-'):
product = "-" + product
elif (tempnum1[0] != '-' and tempnum2[0] == '-'):
product = "-" + product
print("Product of the two numbers is :")
print(product)
# This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to multiply two numbers represented
// as strings.
using System;
using System.Text;
using System.Linq;
public class GFG{
// Driver Code
static public void Main (){
String num1 = "1235421415454545454545454544";
String tempnum1 = num1;
String num2 = "1714546546546545454544548544544545";
String tempnum2 = num2;
// Check condition if one string is negative
if (num1[0] == '-' && num2[0] != '-') {
num1 = num1.Substring(1);
}else{
if (num1[0] != '-' && num2[0] == '-') {
num2 = num2.Substring(1);
}else{
if (num1[0] == '-' && num2[0] == '-') {
num1 = num1.Substring(1);
num2 = num2.Substring(1);
}
}
}
String s1 = new string(num1.Reverse().ToArray());
String s2 = new string(num2.Reverse().ToArray());
int[] m = new int[s1.Length + s2.Length];
// Go from right to left in num1
for (int i = 0; i < s1.Length; i++) {
// Go from right to left in num2
for (int j = 0; j < s2.Length; j++) {
int x = int.Parse((s1[i]-'0').ToString());
int y = int.Parse((s2[j]-'0').ToString());
m[i + j] += (x*y);
}
}
String product = "";
// Multiply with current digit of first number
// and add result to previously stored product
// at current position.
for (int i = 0; i < m.Length; i++) {
int digit = m[i] % 10;
int carry = m[i] / 10;
if (i + 1 < m.Length) {
m[i + 1] += carry;
}
product = digit.ToString() + product;
}
// ignore '0's from the right
while (product.Length > 1 && product[0] == '0') {
product = product.Substring(1);
}
// Check condition if one string is negative
if (tempnum1[0] == '-' && tempnum2[0] != '-') {
product = new StringBuilder(product).Insert(0, '-').ToString();
}else{
if (tempnum1[0] != '-' && tempnum2[0] == '-') {
product = new StringBuilder(product).Insert(0, '-').ToString();
}
}
Console.Write("Product of the two numbers is :\n" + product);
}
}
// This code is contributed by shruti456rawal
Javascript
// Javascript program to implement the approach
let num1 = "1235421415454545454545454544";
let tempnum1 = num1;
let num2 = "1714546546546545454544548544544545";
let tempnum2 = num2;
// Check condition if one string is negative
if (num1[0] == '-' && num2[0] != '-') {
num1 = num1.substring(1);
}
else if (num1[0] != '-' && num2[0] == '-') {
num2 = num2.substring(1);
}
else if (num1[0] == '-' && num2[0] == '-') {
num1 = num1.substring(1);
num2 = num2.substring(1);
}
let s1 = num1.split("");
let s2 = num2.split("");
s1.reverse();
s2.reverse();
let m = new Array(s1.length + s2.length).fill(0);
// Go from right to left in num1
for (var i = 0; i < s1.length; i++)
{
// Go from right to left in num2
for (var j = 0; j < s2.length; j++) {
m[i + j] = m[i + j]
+ (parseInt(s1[i]) * (parseInt(s2[j])));
}
}
let product = "";
// Multiply with current digit of first number
// and add result to previously stored product
// at current position.
for (var i = 0; i < m.length; i++) {
let digit = m[i] % 10;
let carry = Math.floor(m[i] / 10);
if (i + 1 < m.length) {
m[i + 1] = m[i + 1] + carry;
}
product = digit.toString() + product;
}
// ignore '0's from the right
while (product.length > 1 && product[0] == '0') {
product = product.substring(1);
}
// Check condition if one string is negative
if (tempnum1[0] == '-' && tempnum2[0] != '-') {
product = "-" + product;
}
else if (tempnum1[0] != '-' && tempnum2[0] == '-') {
product = "-" + product;
}
console.log("Product of the two numbers is :");
console.log(product);
// This code is contributed by phasing17
Producción:
2118187521397235888154583183918321221520083884298838480662480
Complejidad de tiempo: O (m * n), donde m y n son la longitud de dos números que deben multiplicarse.
Espacio auxiliar: O(m+n), donde m y n son la longitud de dos números que deben multiplicarse.
Artículo relacionado:
Algoritmo de Karatsuba para la multiplicación rápida
Este artículo es una contribución de Aditya Kumar . 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