IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    67. Add Binary

    10k发表于 2023-09-04 00:00:00
    love 0

    Question

    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.

    Algorithm

    Easy question but you need to find some pattern here.

    For each digit you do the math you will get result number 0, 1, 2, 3.

    0 is all digit is 0 and no carry from previous adding;

    1 and 2 is some intermediate result ;

    3 is Both number from two string is 1 and we have a carry digit.

    For a specific digit, the final number is the previous result module 2 and the carry is the previous result divide 2. This is actually the process of decimal turn to binary.

    Code

    class Solution {
        public String addBinary(String a, String b) {
            String res = "";
            int i = a.length() - 1, j = b.length() - 1; 
            int carry = 0;
            
            while (i >= 0 && j >= 0) {
                int ia = a.charAt(i) - '0';
                int ib = b.charAt(j) - '0';
                int cur = (ia + ib + carry) % 2;
                carry = (ia + ib + carry) / 2;
                res = String.valueOf(cur) + res;
                i--;
                j--;
            }
            while (i < 0 && j >= 0) {
                int ib = b.charAt(j) - '0';
                int cur = (ib + carry) % 2;
                carry = (ib + carry) / 2;
                res = String.valueOf(cur) + res;
                j--;
            } 
            while (j < 0 && i >= 0) {
                int ia = a.charAt(i) - '0';
                int cur = (ia + carry) % 2;
                carry = (ia + carry) / 2;
                res = String.valueOf(cur) + res;
                i--;
            }
            if (carry == 1) {
                res = "1" + res;
            }
            return res;
        }
    }
    


沪ICP备19023445号-2号
友情链接