Leetcode – Add Binary

Name: Add Binary
Difficulty: Easy
Description: Given two binary strings a and b, return their sum as a binary string.

Example:

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

This one stretched the memory. We add bits from right to left, bit by bit, so the first thing we need to do is reverse the string so we can proceed from left to right. Looping through the string, we convert the ascii 1 or 0 to a number and add them, plus our carry. We then calculate the new carry. We use modulas to determine if the total is 3 or 2, in which case our value is 1, else it is 0. Our value is added to our string, but we prefix to output in the correct order.

string addBinary(string a, string b) {
    string result = "";

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    int n = max(a.length(), b.length());
    int carry = 0;

    for (int i = 0; i < n; ++i) {
        int x = i < a.length() ? a[i] - 48 : 0;
        int y = i < b.length() ? b[i] - 48 : 0;

        int total = x + y + carry;
        
        carry = total / 2;

        result = to_string(total % 2) + result;
    }

    return carry == 0 ? result : "1" + result;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s