First Thoughts: rather than convert to decimal and do addition and coverting back to binary, might be easier to do binary addition in the first place. this can be done by converting the string characters into array list of integers. By adding to the first of the array list, it will be easier to do calculations in the right digit-position order. Two main variables will be digitValue (current result of two bit addition) and carryIn value (either 0 or 1)
My Solution:
class Solution {
public String addBinary(String a, String b) {
ArrayList<Integer> num = new ArrayList<>();
ArrayList<Integer> op1 = new ArrayList<>();
for (char c: a.toCharArray()) op1.add(0, c-'0');
ArrayList<Integer> op2 = new ArrayList<>();
for (char c: b.toCharArray()) op2.add(0, c-'0');
if (op1.size()>op2.size()) {
while(op1.size()!=op2.size()) op2.add(0);
}
if (op2.size()>op1.size()) {
while (op1.size()!=op2.size()) op1.add(0);
}
int carryIn = 0;
while (op1.size()>0 && op2.size()>0) {
int digitVal = op1.remove(0) + op2.remove(0);
if (carryIn != 0) {
digitVal += carryIn;
carryIn = 0;
}
if (digitVal>1) {
digitVal -= 2;
carryIn = 1;
}
num.add(0, digitVal);
System.out.println(num);
}
if (carryIn!=0) num.add(0, 1);
String result = "";
for (int n : num) result += n;
return result;
}
}Improved Solution (Logical Operators):
current digit answer is XOR result, if carryIn present if answer full -> left shift by one
import java.math.BigInteger;
Class Solution {
public String addBinary (String a, String b) {
BigInteger x = new BigInteger (a, 2);
BigInteger y = new BigInteger (b, 2);
BigInteger zero = new BigInteger ("0", 2);
BigInteger carry, answer;
while (y.compareTo(zero) != 0) {
answer = x.xor(y);
carry = x.and(y).shiftLeft(1);
x = answer;
y = carry;
}
return x.toString(2);
}
}Catch Point:
- 만약 더하기 사용하고 싶다면 arrayList size 맞춰줘야한다 (더 긴 리스트 기준으로 짧은 리스트는 부족한만큼 0으로 채워준다, 둘의 길이가 같아질때까지) -> while loop의 조건 잘 확인 필요. 위치를 잘 확인해야한다 (앞에서부터 요소를 붙여야 하는지)
- BigInteger 라는 library import 해서 사용해도 된다. 근데 중요한건 logical operator로 결과 도출할 수 있다.
