Welcome to Subscribe On Youtube

67. Add Binary

Description

Given two binary strings a and b, return their sum as a binary string.

 

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

 

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Solutions

Solution 1: Simulation

We use a variable $carry$ to record the current carry, and two pointers $i$ and $j$ to point to the end of $a$ and $b$ respectively, and add them bit by bit from the end to the beginning.

The time complexity is $O(\max(m, n))$, where $m$ and $n$ are the lengths of strings $a$ and $b$ respectively. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript
• C#
• RenderScript

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

• class Solution {
  public:
      string addBinary(string a, string b) {
          string ans;
          int i = a.size() - 1, j = b.size() - 1;
          for (int carry = 0; i >= 0 || j >= 0 || carry; --i, --j) {
              carry += (i >= 0 ? a[i] - '0' : 0) + (j >= 0 ? b[j] - '0' : 0);
              ans.push_back((carry % 2) + '0');
              carry /= 2;
          }
          reverse(ans.begin(), ans.end());
          return ans;
      }
  };
  

• class Solution:
      def addBinary(self, a: str, b: str) -> str:
          ans = []
          i, j, carry = len(a) - 1, len(b) - 1, 0
          while i >= 0 or j >= 0 or carry:
              carry += (0 if i < 0 else int(a[i])) + (0 if j < 0 else int(b[j]))
              carry, v = divmod(carry, 2)
              ans.append(str(v))
              i, j = i - 1, j - 1
          return "".join(ans[::-1])
  
  

• func addBinary(a string, b string) string {
  	i, j := len(a)-1, len(b)-1
  	ans := []byte{}
  	for carry := 0; i >= 0 || j >= 0 || carry > 0; i, j = i-1, j-1 {
  		if i >= 0 {
  			carry += int(a[i] - '0')
  		}
  		if j >= 0 {
  			carry += int(b[j] - '0')
  		}
  		ans = append(ans, byte(carry%2+'0'))
  		carry /= 2
  	}
  	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
  		ans[i], ans[j] = ans[j], ans[i]
  	}
  	return string(ans)
  }
  

• function addBinary(a: string, b: string): string {
      let i = a.length - 1;
      let j = b.length - 1;
      let ans: number[] = [];
      for (let carry = 0; i >= 0 || j >= 0 || carry; --i, --j) {
          carry += (i >= 0 ? a[i] : '0').charCodeAt(0) - '0'.charCodeAt(0);
          carry += (j >= 0 ? b[j] : '0').charCodeAt(0) - '0'.charCodeAt(0);
          ans.push(carry % 2);
          carry >>= 1;
      }
      return ans.reverse().join('');
  }
  
  

• public class Solution {
      public string AddBinary(string a, string b) {
          int i = a.Length - 1;
          int j = b.Length - 1;
          var sb = new StringBuilder();
          for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) {
              carry += i >= 0 ? a[i] - '0' : 0;
              carry += j >= 0 ? b[j] - '0' : 0;
              sb.Append(carry % 2);
              carry /= 2;
          }
          var ans = sb.ToString().ToCharArray();
          Array.Reverse(ans);
          return new string(ans);
      }
  }
  

• impl Solution {
      pub fn add_binary(a: String, b: String) -> String {
          let mut i = (a.len() as i32) - 1;
          let mut j = (b.len() as i32) - 1;
          let mut carry = 0;
          let mut ans = String::new();
          let a = a.as_bytes();
          let b = b.as_bytes();
          while i >= 0 || j >= 0 || carry > 0 {
              if i >= 0 {
                  carry += a[i as usize] - b'0';
                  i -= 1;
              }
              if j >= 0 {
                  carry += b[j as usize] - b'0';
                  j -= 1;
              }
              ans.push_str(&(carry % 2).to_string());
              carry /= 2;
          }
          ans.chars().rev().collect()
      }
  }
  
  

All Problems

All Solutions