## Sunday, February 28, 2016

### Multiply Two Big Integers

http://www.zrzahid.com/production-of-big-integers/
```//O(nm)
public static String prod(String str1, String str2){
String res = new String("0");

int count = 0;
for(int i = str2.length()-1; i>=0 ; i--){
int d2 = str2.charAt(i)-'0';

int carry = 0;
StringBuffer prod = new StringBuffer();
for(int j = str1.length()-1; j>=0; j--){
int d1 = str1.charAt(j)-'0';
int p = carry+(d1*d2);
prod.append(p%10);
carry = p/10;
}

if(carry != 0){
prod.append(carry);
}

prod.reverse();

for(int k = 0; k<count; k++){
prod.append(0);
}

count++;
}

return res.toString();
}

//O(n);
private static String add(String str1, String str2){
StringBuffer res = new StringBuffer();

int i = str1.length()-1;
int j = str2.length()-1;
int carry = 0;
while(true){
if(i < 0 && j < 0){
break;
}

int d1 = i < 0 ? 0 : str1.charAt(i--)-'0';
int d2 = j < 0 ? 0 : str2.charAt(j--)-'0';
int sum = d1+d2+carry;

res.append(sum%10);
carry = sum/10;
}

if(carry != 0){
res.append(carry);
}

return res.reverse().toString();
}```