Solution For Add Binary
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:
- Start from the last digit of both the strings.
- Initialize three variables to store carry, sum and result.
- Traverse the strings from the end to the start.
- Calculate the sum of bits at the current index, carry and the previous carry.
- If the sum is 0 or 1, update the carry to 0 and the sum to the value of the sum.
- If the sum is 2 or 3, update the carry to 1 and the sum to the remainder of the sum/2.
- Append the sum to the result string.
- If there is still a carry remaining after the loop iteration, append it to the result.
- 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(); } }
def addBinary(a, b): # 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) { // your code goes here };
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; } }