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

For example,
a = "11"
b = "1"
Return "100".

class Solution {
public:
    string addBinary(string a, string b) {
        int fw = 0;
        string result = "";
        for(int i = a.size()-1,j=b.size()-1;i>=0||j>=0;i--,j--){
            int ag = i>=0?a[i]-'0':0;
            int bg = j>=0?b[j]-'0':0;
            int tmp = (ag+bg+fw)%2;
            fw = (ag+bg+fw)/2;
            
            result = char(tmp+'0')+result;
        }
        if(fw==1){
            result = '1'+result;
        }
        
        return result;
    }
};

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        int b = 0;
        while(i<bits.size()){            
            if(bits[i]==1)
            {
                i=i+2;
                b=0;
            }else{
                i++;
                b=1;
            }
        };
        if(b==0){
            return 0;
        }else {
            return 1; 
        }
    }
};

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

class Solution {
public:
    int addDigits(int num) {
        // while(num/10>0){
        //     int sum = 0;
        //     while(num>0){
        //         sum +=num%10;
        //         num /=10;
        //     }
        //     num = sum;
        // }
        return 1+ (num-1)%9;
    }
};

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution {
public:
    string addStrings(string num1, string num2) {
        int fw = 0;
        string result ="";
        for(int i = num1.size()-1,j = num2.size()-1;i>=0||j>=0;i--,j--){
            int n1 = i>=0 ? num1[i]-'0':0;
            int n2 = j>=0 ? num2[j]-'0':0;
            int tmp = (n1+n2+fw)%10;
            fw = (n1+n2+fw)/10;
            result = char(tmp+'0') + result;
        }
        if(fw){
            result = char(fw +'0')+ result;
        }
        return result;
    }
};