Skip to content

Instantly share code, notes, and snippets.

@wayetan
Last active October 19, 2015 07:16
Show Gist options
  • Save wayetan/9401720 to your computer and use it in GitHub Desktop.
Save wayetan/9401720 to your computer and use it in GitHub Desktop.
Multiply Strings
/**
* Given two numbers represented as strings, return multiplication of the numbers as a string.
* Note: The numbers can be arbitrarily large and are non-negative.
*/
public class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0"))
return "0";
int l1 = num1.length(), l2 = num2.length();
int[] n1 = new int[l1];
int[] n2 = new int[l2];
// convert num1 to number array reversely
for (int i = 0; i < l1; i++) {
n1[l1 - i - 1] = num1.charAt(i) - '0';
}
// convert num2 to number array reversely
for (int i = 0; i < l2; i++) {
n2[l2 - i - 1] = num2.charAt(i) - '0';
}
int sum = 0;
StringBuilder ss = new StringBuilder();
for (int i = 0; i < l1 + l2 - 1; i++) {
for (int j = 0; j <= i; j++) {
if(j < l1 && i - j < l2) {
sum += n1[j] * n2[i - j];
}
}
ss.append((char) (sum % 10 + '0'));
sum /= 10;
}
if (sum > 0)
ss.append((char) (sum + '0'));
String s = ss.reverse().toString();
return s.isEmpty() ? "0" : s;
}
public String multiply(String num1, String num2) {
String n1 = new StringBuilder(num1).reverse().toString();
String n2 = new StringBuilder(num2).reverse().toString();
int[] d = new int[num1.length()+num2.length()];
//multiply each digit and sum at the corresponding positions
for(int i=0; i<n1.length(); i++){
for(int j=0; j<n2.length(); j++){
d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');
}
}
StringBuilder sb = new StringBuilder();
//calculate each digit
for(int i=0; i<d.length; i++){
int mod = d[i]%10;
int carry = d[i]/10;
if(i+1<d.length){
d[i+1] += carry;
}
sb.insert(0, mod);
}
//remove front 0's
while(sb.charAt(0) == '0' && sb.length()> 1){
sb.deleteCharAt(0);
}
return sb.toString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment