leetcode/problems/src/string/MultiplyStrings.java at master · KindleBooks66/leetcode · GitHub

History

73 lines (69 loc) · 2.25 KB

Raw

package string;

/**

* Created by gouthamvidyapradhan on 01/02/2018. Given two non-negative integers num1 and num2

* represented as strings, return the product of num1 and num2.

* <p>Note:

* <p>The length of both num1 and num2 is < 110. Both num1 and num2 contains only digits 0-9. Both

* num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library

* or convert the inputs to integer directly.

* <p>Solution: O(N x M) where N and M are length of strings

public class MultiplyStrings {

/**

* Main method

* @param args

* @throws Exception

public static void main(String[] args) throws Exception {

System.out.println(new MultiplyStrings().multiply("00", "0000"));

}

public String multiply(String num1, String num2) {

if ((num1.length() == 1 && num1.equals("0")) || (num2.length() == 1 && num2.equals("0")))

return "0";

if (num1.length() < num2.length()) return multiply(num2, num1);

String temp2 = "", trail = "";

int carry = 0;

for (int i = 0; i < num1.length(); i++) {

temp2 += "0";

}

for (int i = num1.length() - 1; i >= 0; i--) {

String temp1 = "";

for (int j = num2.length() - 1; j >= 0; j--) {

int prod =

Integer.parseInt(String.valueOf(num2.charAt(j)))

* Integer.parseInt(String.valueOf(num1.charAt(i)));

prod += carry;

temp1 = (prod % 10) + temp1;

carry = (prod / 10);

}

if (carry > 0) {

temp1 = String.valueOf(carry) + temp1;

carry = 0;

}

String temp3 = add(temp1, temp2);

temp2 = temp3.substring(0, temp3.length() - 1);

trail = temp3.substring(temp3.length() - 1, temp3.length()) + trail;

}

return temp2 + trail;

}

private String add(String s1, String s2) {

String result = "";

int carry = 0;

int i = s1.length() - 1, j = s2.length() - 1;

for (; i >= 0 || j >= 0; i--, j--) {

int l = (i >= 0) ? Integer.parseInt(String.valueOf(s1.charAt(i))) : 0;

int r = (j >= 0) ? Integer.parseInt(String.valueOf(s2.charAt(j))) : 0;

int sum = l + r + carry;

carry = sum / 10;

result = sum % 10 + result;

}

if (carry > 0) {

result = carry + result;

}

return result;

}

leetcode/problems/src/string/MultiplyStrings.java at master · KindleBooks66/leetcode · GitHub

Uh oh!

Expand file tree

Breadcrumbs

MultiplyStrings.java

Latest commit

History

Breadcrumbs

MultiplyStrings.java

File metadata and controls