-
Notifications
You must be signed in to change notification settings - Fork 0
/
MultiplyString.java
71 lines (59 loc) · 1.82 KB
/
MultiplyString.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package string;
import java.util.ArrayList;
/**
* Given two numbers represented as strings, return multiplication of the numbers as a string.
* <p>
* Note: The numbers can be arbitrarily large and are non-negative.<br>
* Note2: Your answer should not have leading zeroes. For example, 00 is not a valid answer.
* <p>
* For example, given strings <code>"12", "10"</code>, your answer should be <code>"120"</code>.
* <p>
* <strong>NOTE:</strong> DO NOT USE BIG INTEGER LIBRARIES.
*
* @author Tzipora Ziegler
*
* @see https://www.interviewbit.com/problems/multiply-strings/
*
*/
public class MultiplyString {
public String multiply(String a, String b) {
if ("0".equals(a) || "0".equals(b))
{
return "0";
}
final ArrayList<Integer> productArray = new ArrayList<Integer>();
int moveOver = 1;
for (int j = b.length() - 1; j >= 0; j--) {
int leftover = 0;
int position = productArray.size() - moveOver++;
final int bottomDigit = Character.getNumericValue(b.charAt(j));
for (int i = a.length() - 1; i >= 0; i--) {
final int topDigit = Character.getNumericValue(a.charAt(i));
final int currentDigit = position >= 0 ? productArray.get(position) : 0;
final int product = bottomDigit * topDigit + leftover + currentDigit;
final int placeNumber = product % 10;
leftover = product / 10;
if (position >= 0) {
productArray.set(position, placeNumber);
}
else {
productArray.add(0, placeNumber);
}
position--;
}
if (leftover != 0) {
productArray.add(0, leftover);
}
}
return printList(productArray);
}
private String printList(ArrayList<Integer> list) {
final StringBuilder builder = new StringBuilder();
for (final int digit : list) {
if (builder.length() > 0 || digit != 0) {
builder.append(digit);
}
}
return builder.toString();
}
}