Space complexity of the "add two binary strings" challenge

Question

I was solving this problem of "adding two string binary numbers" and came up with the following algorithm. I am trying to analyze its time and space complexity. While I was satisfied with its time complexity which is \$O(n)\,ドル I am not really sure about the space. I think the space complexity is \$O(n)\$ as well but I might be wrong because of the StringBuilder usage here.

public String sumOfBinary(String x, String y) {
 if((x.length == 0 && y.length == 0) || (x == null && y == null)) 
 return;
 int i = x.length - 1, j = y.length - 1, carry = 0;
 StringBuilder sb = new StringBuilder();
 while(i > = 0 || j >= 0) {
 int sum = carry;
 if(i >= 0) {
 sum+= x.charAt(i--) - '0';
 }
 if(j>=0) {
 sum+=y.charAt(j--) - '0';
 }
 sb.append(sum%2);
 carry = sum/2;
 }
 if(carry!=0) {
 sb.append(carry);
 }
 return sb.reverse().toString();
}

It would be awesome if someone could review the code and let me know if there is any other better way to do this, along with what the space complexity is in the algorithm.

• Sharon Ben Asher: in the first if statement, you need to reverse the order if checks (check for null first) otherwise you will get NPE on checking length

Answer 1

Here's some other points to consider.

Checking for empty string and null seems to be redundant. The compiler treats them the same.

Your check for null, only checks if both are null. For completion it would be better to also check if either is null.

I think it would be more performant to use a char array set to the longest length possible(length of longest string plus 1) and change the value at each index, rather than constantly appending to the StringBuilder.

You aren't checking for malformed strings.

You aren't handling strings of different lengths.

With all these taken into consideration your code could look something like this:

final static char ZERO_CHAR_VALUE = '0';
final static char ONE_CHAR_VALUE = '1';
final static char DEFAULT_CHAR_VALUE = '0円';
public static String AddBinary(String inValA, String inValB) {
 if (inValA == null) {
 if (inValB == null) {
 return null;
 }
 return inValB;
 }
 if (inValB == null) {
 return inValA;
 }
 int aIndex = inValA.length() - 1;
 int bIndex = inValB.length() - 1;
 int longestLength = Math.max(aIndex, bIndex) + 2;
 char[] tempOutVal = new char[longestLength];
 int tempOutIndex = tempOutVal.length - 1;
 char aTemp;
 char bTemp;
 for (; aIndex >= 0 && bIndex >= 0; aIndex--, bIndex--, tempOutIndex--) {
 aTemp = inValA.charAt(aIndex);
 BinaryCharValidator(aTemp, inValA);
 bTemp = inValB.charAt(bIndex);
 BinaryCharValidator(bTemp, inValB);
 SetValue(aTemp, bTemp, tempOutVal, tempOutIndex);
 }
 if (aIndex >= 0) {
 for (; aIndex >= 0; aIndex--, tempOutIndex--) {
 aTemp = inValA.charAt(aIndex);
 BinaryCharValidator(aTemp, inValA);
 bTemp = ZERO_CHAR_VALUE;
 SetValue(aTemp, bTemp, tempOutVal, tempOutIndex);
 }
 }
 if (bIndex >= 0) {
 for (; bIndex >= 0; bIndex--, tempOutIndex--) {
 aTemp = ZERO_CHAR_VALUE;
 bTemp = inValB.charAt(bIndex);
 BinaryCharValidator(bTemp, inValB);
 SetValue(aTemp, bTemp, tempOutVal, tempOutIndex);
 }
 }
 return new String(tempOutVal);
}
public static void SetValue(char aVal, char bVal, char[] outVal, int outIndex) {
 if (outVal[outIndex] == DEFAULT_CHAR_VALUE) {
 outVal[outIndex] = ZERO_CHAR_VALUE;
 }
 int aTemp = aVal - ZERO_CHAR_VALUE;
 int bTemp = bVal - ZERO_CHAR_VALUE;
 int outTemp = outVal[outIndex] - ZERO_CHAR_VALUE;
 int sum = aTemp + bTemp + outTemp;
 outVal[outIndex] = (char) ((sum % 2) + ZERO_CHAR_VALUE);
 if (sum > 1) {
 outVal[outIndex - 1] = ONE_CHAR_VALUE;
 } else {
 outVal[outIndex -1] = ZERO_CHAR_VALUE;
 }
}
public static void BinaryCharValidator(char toCheck, String input) {
 if (!(toCheck == ZERO_CHAR_VALUE || toCheck == ONE_CHAR_VALUE)) {
 throw new IllegalArgumentException(String.format("Malformed string(only 1's and 0's allowed). The string is \"%s0\"", input));
 }
}

• ShellZero: Absolutely brilliant! Thank you for taking time in solving the problem :)
• user33306: Thanks. Something else to consider. Since StringBuilder.reverse(), creates another StringBuilder and would require a second iteration over the data, I think both the time and space complexity, of your original code, would be O(2n)
• ShellZero: O(2n) = O(n) as the constant multiplier is not going to make any difference in the Big O :)
• user33306: @ShellZero - There was a bug in the original code. It would leave whitespace at index 0 if there wasn't any carry. I've changed it to always have either a '1' or a '0' at index 0.
• ShellZero: @RobAu Right. Will keep that in mind. :)

Answer 2

I agree with you, space complexity should be \$O(n)\,ドル using StringBuilder should not matter because, internally it would store char in an array which would expand / shrink as needed.

Now some code-reviews.

Error check:

1. Null check? x or y could be null. This (x == null || y == null) looks better.

2. Your code says "sumofbinary", but what if your string was "123" + "543"?

Name check:

1. sb is not a professional name, call it sum.

Syntax check:

1. while(i > = 0 || j >= 0) .. there is a space > = for i > = 0, but not for j.

Misc:

1. StringBuilder can be marked final.

2. You end for loop when both i & j are 0. This has a drawback, if i is longer than j, you would waste error checking if (j> 0).