Given two numbers as strings s1 and s2, calculate their product.
Note: The numbers can be negative. There can be zeros in the beginning of the numbers.
Examples:
Input: s1 = "0033", s2 = "2"
Output: "66"
Explanation: 33 * 2 = 66Input: s1 = "11", s2 = "23"
Output: "253"
Explanation: 11 * 23 = 253Input: s1 = "123", s2 = "0"
Output: "0"
Explanation: Anything multiplied by 0 is equal to 0.
Try it on GfG Practice
Approach: Using String Manipulation - (m * n) Time and O(m + n) Space
The idea is to simulate the manual multiplication process using string manipulation and integer arithmetic, while considering the signs of the input numbers and properly handling carries.
Step By Step implementation:
- Handling Zeroes:
-> return 0 if a=0 or b=0. - Handling Negative Numbers:
-> it checks if the first character of each string is '-'. If either a or b is negative, it toggles the negative flag and removes the negative sign from the respective string. - The product list is initialized with zeros, where the length of the list is set to accommodate the potential maximum length of the product string.
- We will be using two nested loops.
-> The outer loop iterates through the characters of string b from right to left, treating them as digits.
-> The inner loop iterates through the characters of string a from right to left, treating them as digits. - Multiplying and Carrying:
-> Within the inner loop, it calculates the product of the current digits from a and b, adds any carry from previous calculations, and updates the corresponding position in the product list. It also calculates a new carry for the next iteration. - After the inner loop completes, it handles any remaining carry by propagating it to the previous positions in the product list.
- It then constructs a result string res by joining the elements of the product list.
- It removes any leading zeros from the res string.
- If the negative flag is set, it adds a negative sign to the res string.
- Finally, it returns the res string, which represents the product of the two input numbers.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string multiplyStrings(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size();
if (n1 == 0 || n2 == 0)
return "0";
// check if string are negative
int nn = 1, mm = 1;
if (s1[0] == '-')
nn = -1;
if (s2[0] == '-')
mm = -1;
int isNeg = nn * mm;
// will keep the result number in
// vector in reverse order
vector<int> result(n1 + n2, 0);
// index by s1
int i1 = 0;
// index by s2
int i2 = 0;
// go from right to left by s1
for (int i = n1 - 1; i >= 0; i--) {
if (s1[i] == '-')
continue;
int carry = 0;
int n1 = s1[i] - '0';
i2 = 0;
// go from right to left by s2
for (int j = n2 - 1; j >= 0; j--) {
if (s2[j] == '-')
continue;
int n2 = s2[j] - '0';
// multiply and add this result
// to the existing result
int sum = n1 * n2 + result[i1 + i2] + carry;
// carry for next iteration
carry = sum / 10;
// store result
result[i1 + i2] = sum % 10;
i2++;
}
// store carry in next cell
if (carry > 0)
result[i1 + i2] += carry;
i1++;
}
// 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 s1 or s2 were '0'
if (i == -1)
return "0";
// generate the result string
string s = "";
while (i >= 0)
s += to_string(result[i--]);
// if negative
if (isNeg == -1)
s = "-" + s;
return s;
}
int main() {
string s1 = "0033", s2 = "2";
cout << multiplyStrings(s1, s2);
return 0;
}
class GfG {
static String multiplyStrings(String s1, String s2) {
int n1 = s1.length(), n2 = s2.length();
if (n1 == 0 || n2 == 0)
return "0";
// check if string are negative
int nn = 1, mm = 1;
if (s1.charAt(0) == '-')
nn = -1;
if (s2.charAt(0) == '-')
mm = -1;
int isNeg = nn * mm;
// will keep the result number in
// vector in reverse order
int[] result = new int[n1 + n2];
// index by s1
int i1 = 0;
// index by s2
int i2 = 0;
// go from right to left by s1
for (int i = n1 - 1; i >= 0; i--) {
if (s1.charAt(i) == '-')
continue;
int carry = 0;
int n1Digit = s1.charAt(i) - '0';
i2 = 0;
// go from right to left by s2
for (int j = n2 - 1; j >= 0; j--) {
if (s2.charAt(j) == '-')
continue;
int n2Digit = s2.charAt(j) - '0';
// multiply and add this result
// to the existing result
int sum = n1Digit * n2Digit + result[i1 + i2] + carry;
// carry for next iteration
carry = sum / 10;
// store result
result[i1 + i2] = sum % 10;
i2++;
}
// store carry in next cell
if (carry > 0)
result[i1 + i2] += carry;
i1++;
}
// 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 s1 or s2 were '0'
if (i == -1)
return "0";
// generate the result string
String s = "";
while (i >= 0)
s += Integer.toString(result[i--]);
// if negative
if (isNeg == -1)
s = "-" + s;
return s;
}
public static void main(String[] args) {
String s1 = "0033", s2 = "2";
System.out.println(multiplyStrings(s1, s2));
}
}
def multiplyStrings(a, b):
# Checking if either of
# the strings is zero
if a == '0' or b == '0':
return '0'
# Setting a variable to keep track
# of the sign of the product
negative = False
# Checking if the first
# string is negative
if a[0] == '-':
negative = not negative
a = a[1:]
# Checking if the second
# string is negative
if b[0] == '-':
negative = not negative
b = b[1:]
# Initializing a list to
# store the product
product = [0 for _ in range(len(a) + len(b))]
# Multiplying each digit of the
# second string with each digit
# of the first string
for i in range(len(b) - 1, -1, -1):
digit1 = int(b[i])
carry = 0
# Iterating over each digit
# of the first string
for j in range(len(a) - 1, -1, -1):
digit2 = int(a[j])
# Adding the product of the
# digits with the carry
product[i + j + 1] += digit1 * digit2 + carry
carry = product[i + j + 1] // 10
product[i + j + 1] = product[i + j + 1] % 10
# Handling any remaining carry
nextIndex = i
while carry:
product[nextIndex] += carry
carry = product[nextIndex] // 10
product[nextIndex] = product[nextIndex] % 10
nextIndex -= 1
# Converting the product list to a string
res = ''.join(str(x) for x in product)
# Removing leading zeroes from the product
zeroes = 0
while zeroes < len(res) - 1 and res[zeroes] == '0':
zeroes += 1
res = res[zeroes:]
# Adding the negative sign if necessary
if negative and res != "0":
res = '-' + res
# Returning the final product
return res
if __name__ == '__main__':
s1 = "0033"
s2 = "2"
print(multiplyStrings(s1, s2))
using System;
using System.Text;
class GfG {
static string multiplyStrings(string s1, string s2) {
int n1 = s1.Length, n2 = s2.Length;
if(n1 == 0 || n2 == 0)
return "0";
// check if string are negative
int nn = 1, mm = 1;
if(s1[0] == '-')
nn = -1;
if(s2[0] == '-')
mm = -1;
int isNeg = nn * mm;
// will keep the result number in
// vector in reverse order
int[] result = new int[n1 + n2];
for (int i = 0; i < result.Length; i++)
result[i] = 0;
// index by s1
int i1 = 0;
// index by s2
int i2 = 0;
// go from right to left by s1
for (int i = n1 - 1; i >= 0; i--) {
if(s1[i] == '-')
continue;
int carry = 0;
int n1Digit = s1[i] - '0';
i2 = 0;
// go from right to left by s2
for (int j = n2 - 1; j >= 0; j--) {
if(s2[j] == '-')
continue;
int n2Digit = s2[j] - '0';
// multiply and add this result
// to the existing result
int sum = n1Digit * n2Digit + result[i1 + i2] + carry;
// carry for next iteration
carry = sum / 10;
// store result
result[i1 + i2] = sum % 10;
i2++;
}
// store carry in next cell
if(carry > 0)
result[i1 + i2] += carry;
i1++;
}
// ignore '0's from the right
int k = result.Length - 1;
while(k >= 0 && result[k] == 0)
k--;
// if all were '0's - means either
// both or one of s1 or s2 were '0'
if(k == -1)
return "0";
// generate the result string
StringBuilder s = new StringBuilder();
while(k >= 0)
s.Append(result[k--]);
// if negative
if(isNeg == -1)
s.Insert(0, "-");
return s.ToString();
}
static void Main() {
string s1 = "0033";
string s2 = "2";
Console.WriteLine(multiplyStrings(s1, s2));
}
}
function multiplyStrings(s1, s2) {
let n1 = s1.length, n2 = s2.length;
if(n1 === 0 || n2 === 0)
return "0";
// check if string are negative
let nn = 1, mm = 1;
if(s1[0] === '-')
nn = -1;
if(s2[0] === '-')
mm = -1;
let isNeg = nn * mm;
// will keep the result number in
// vector in reverse order
let result = new Array(n1 + n2).fill(0);
// index by s1
let i1 = 0;
// index by s2
let i2 = 0;
// go from right to left by s1
for (let i = n1 - 1; i >= 0; i--) {
if (s1[i] === '-')
continue;
let carry = 0;
let n1Digit = parseInt(s1[i]);
i2 = 0;
// go from right to left by s2
for (let j = n2 - 1; j >= 0; j--) {
if (s2[j] === '-')
continue;
let n2Digit = parseInt(s2[j]);
// multiply and add this result
// to the existing result
let sum = n1Digit * n2Digit + result[i1 + i2] + carry;
// carry for next iteration
carry = Math.floor(sum / 10);
// store result
result[i1 + i2] = sum % 10;
i2++;
}
// store carry in next cell
if (carry > 0)
result[i1 + i2] += carry;
i1++;
}
// ignore '0's from the right
let i = result.length - 1;
while(i >= 0 && result[i] === 0)
i--;
// if all were '0's - means either
// both or one of s1 or s2 were '0'
if(i === -1)
return "0";
// generate the result string
let s = "";
while(i >= 0)
s += result[i--].toString();
// if negative
if(isNeg === -1)
s = "-" + s;
return s;
}
// Driver Code
let s1 = "0033";
let s2 = "2";
console.log(multiplyStrings(s1, s2));
Output
66
Related Article :
Karatsuba algorithm for fast multiplication