## Similar Problems

### Valid Phone Numbers

Problem Statement:

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example:

Input: a = “1010”, b = “1011”
Output: “10101”

Explanation:
1010
1011

10101

Solution:

For the given problem, we can take two pointers starting from the end of the binary strings a and b, to calculate the sum bit by bit, and then carry the remainder to the next bit. If the sum is greater than 1, (1+1) would indicate that a carry (1) is required for the next bit.

Algorithm:

1. Start from the last digit of both the strings.
2. Initialize three variables to store carry, sum and result.
3. Traverse the strings from the end to the start.
4. Calculate the sum of bits at the current index, carry and the previous carry.
5. If the sum is 0 or 1, update the carry to 0 and the sum to the value of the sum.
6. If the sum is 2 or 3, update the carry to 1 and the sum to the remainder of the sum/2.
7. Append the sum to the result string.
8. If there is still a carry remaining after the loop iteration, append it to the result.
9. Reverse the resultant string and return the answer.

A code snippet in Python is given below:

def addBinary(a: str, b: str) -> str:
i, j = len(a)-1, len(b)-1
carry, res = 0, ''
while i >= 0 or j >= 0:
cur_sum = carry
if i >= 0:
cur_sum += int(a[i])
i -= 1
if j >= 0:
cur_sum += int(b[j])
j -= 1
if cur_sum < 2:
carry = 0
res += str(cur_sum)
else:
carry = 1
res += str(cur_sum % 2)
if carry:
res += str(carry)
return res[::-1]

Time Complexity: O(n), where n is the length of the longest input string.

Space Complexity: O(n), where n is the length of the resultant string.

## Step by Step Implementation For Add Binary

public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() -1, carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (j >= 0) sum += b.charAt(j--) - '0';
if (i >= 0) sum += a.charAt(i--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
if (carry != 0) sb.append(carry);
return sb.reverse().toString();
}
}

# initialize result variable to store sum
result = ""

# initialize carry variable to store carry
carry = 0

# loop through both strings starting from the end
for i in range(1, max(len(a), len(b)) + 1):

# get the ith digit from both strings
# if the string is shorter than i, assume digit is 0
a_digit = int(a[-i]) if i <= len(a) else 0
b_digit = int(b[-i]) if i <= len(b) else 0

# sum the digits and carry
digit_sum = a_digit + b_digit + carry

# if the sum is 2 or 3, set carry to 1
if digit_sum >= 2:
carry = 1

# if the sum is 1 or 3, add 1 to the result
if digit_sum % 2 == 1:
result = "1" + result

# if the sum is 0 or 2, add 0 to the result
else:
result = "0" + result

# if carry is 1 after finishing the loop, add 1 to the result
if carry == 1:
result = "1" + result

return result
var addBinary = function(a, b) {
};
class Solution {
public:
string addBinary(string a, string b) {
string result = "";
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (i >= 0) {
sum += a[i] - '0';
i--;
}
if (j >= 0) {
sum += b[j] - '0';
j--;
}
result = to_string(sum % 2) + result;
carry = sum / 2;
}
if (carry == 1) {
result = "1" + result;
}
return result;
}
};
public class Solution {
public string AddBinary(string a, string b) {
// initialize result string to empty
string result = "";

// initialize carry to 0
int carry = 0;

// initialize index to the end of both strings
int i = a.Length - 1;
int j = b.Length - 1;

// while we haven't reached the beginning of either string
while (i >= 0 || j >= 0) {
// initialize sum to carry
int sum = carry;

// if we haven't reached the beginning of string a, add the current character to sum
if (i >= 0) {
sum += a[i] - '0';
}

// if we haven't reached the beginning of string b, add the current character to sum
if (j >= 0) {
sum += b[j] - '0';
}

// if sum is 0 or 1, add sum to result and set carry to 0
// otherwise, add 1 to result and set carry to 1
result = (sum % 2).ToString() + result;
carry = sum / 2;

// move to the next character in both strings
i--;
j--;
}

// if carry is 1, add it to the front of the result string
if (carry == 1) {
result = "1" + result;
}

// return the result string
return result;
}
}

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]