Problem: Given two binary strings a and b, return their sum as a binary string.
Example:
Input: a = "11", b = "1" Output: "100"
Input: a = "1010", b = "1011" Output: "10101"
Approach: Nothing much to discuss here. Its an easy problem to solve. Just look at the implementation to understand the approach.
Implementation in C#:
public string AddBinary(string a, string b)
{
int lenA = a.Length;
int lenB = b.Length;
int maxLen = Math.Max(lenA, lenB);
char[] res = new char[maxLen];
int i = lenA - 1, j = lenB - 1;
int k = maxLen - 1;
int carry = 0;
while(i >= 0 && j >= 0)
{
char add = '0';
if (a[i] == '1' && b[j] == '1')
{
add ='0';
if (carry == 1)
{
add = '1';
}
carry = 1;
}
else if (a[i] == '0' && b[j] == '0')
{
add = '0';
if (carry == 1)
{
add = '1';
}
carry = 0;
}
else
{
add = '1';
if (carry == 1)
{
add = '0';
carry = 1;
}
else
{
carry = 0;
}
}
res[k--] = add;
--i;
--j;
}
if (i >= 0)
{
this.HandleSingleNum(a, i, res, k, ref carry);
}
if (j >= 0)
{
this.HandleSingleNum(b, j, res, k, ref carry);
}
string result = carry == 1 ?
"1" + new string(res) :
new string(res);
return result;
}
private void HandleSingleNum(
string num,
int numIndex,
char[] result,
int resIndex,
ref int carry)
{
while(numIndex >= 0)
{
if (num[numIndex] == '0')
{
if (carry == 1)
{
result[resIndex--] = '1';
}
else
{
result[resIndex--] = '0';
}
carry = 0;
}
else
{
if (carry == 1)
{
result[resIndex--] = '0';
carry = 1;
}
else
{
result[resIndex--] = '1';
carry = 0;
}
}
--numIndex;
}
}
Complexity: O(n) where n is max of length of a and length of b.
No comments:
Post a Comment