Facebook Interview Question for Android Engineers


Country: UK, London
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

My naive implementation. (Kotlin)

fun addBinary(addendumLeft: String, addendumRight: String): String {
var i = addendumLeft.length-1
var j = addendumRight.length-1
/* Handling edge cases */
if(addendumLeft.isEmpty() && addendumRight.isNotEmpty())
return addendumRight
else if(addendumRight.isEmpty() && addendumLeft.isNotEmpty())
return addendumLeft
else if(addendumLeft.isEmpty() && addendumRight.isEmpty())
return ""

/* Implementation */
val result = StringBuilder()
var carryOn = false
while (i >= 0 || j >= 0) {
if(i < 0 || j < 0)
{
val bin = if(j < 0) addendumLeft[i] else addendumRight[j]
if(carryOn) {
if(bin == '1')
result.insert(0,'0')
else {
result.insert(0,'1')
carryOn = false
}
} else
result.insert(0, bin)

} else {
if(addendumLeft[i] == '0' && addendumRight[j] == '1' ||
addendumLeft[i] == '1' && addendumRight[j] == '0') {
if(carryOn)
result.insert(0, '0')
else
result.insert(0, '1')
}
else if(addendumLeft[i] == '1' && addendumRight[j] == '1') {
if(carryOn)
result.insert(0, '1')
else {
carryOn = true
result.insert(0, '0')
}
}
else {
if(carryOn) {
result.insert(0, '1')
carryOn = false
} else
result.insert(0,'0')
}
}

if(i >= 0)
i--
if(j >= 0)
j--
}

if(carryOn)
result.insert(0, '1')

return result.toString()
}

Any more elegant solution?

- fruktoed August 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Improved solution

fun addBinary(addendumLeft: String, addendumRight: String): String {
var i = addendumLeft.length-1
var j = addendumRight.length-1
/* Handling edge cases */
if(addendumLeft.isEmpty() && addendumRight.isNotEmpty())
return addendumRight
else if(addendumRight.isEmpty() && addendumLeft.isNotEmpty())
return addendumLeft
else if(addendumLeft.isEmpty() && addendumRight.isEmpty())
return ""

/* Implementation */
val result = StringBuilder()
var sum = 0
while (i >= 0 || j >= 0 || sum == 1) {

sum += if(i >= 0) addendumLeft[i] - '0' else 0
sum += if(j >= 0) addendumRight[j] - '0' else 0

result.insert(0, sum % 2)

sum /= 2

if(i >= 0)
i--
if(j >= 0)
j--
}

return result.toString()
}

Thanks to GeeksforGeeks

- fruktoed August 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here.

def bin_add( n1, n2 ){
  /* 
  n1 digit, n2 digit, carry digit from previous ->
  carry, resulting digit 
  */
  RULES = { '000' : '00', 
            '001' : '01', 
            '010' : '01',
            '011' : '10',
            '100' : '01', 
            '101' : '10',
            '110' : '10',
            '111' : '11' }
  min_size = size(n2)
  max_size = size(n1)
  if ( max_size < min_size ){
    #(n2,n1) = [n1, n2] // swap 
  }
  carry = '0'
  result = ""
  // when both are same size 
  i = min_size -1
  j = max_size -1
  while ( i >=0 ){
    input = str("%s%s%s", n1[j],n2[i], carry)
    i -= 1 
    j -= 1
    output = RULES[input]
    carry = output[0]
    result = str( "%s%s", output[1],  result )
  }
  while ( j >= 0) {
    input = str("%s0%s", n1[j],carry) 
    j -= 1
    output = RULES[input]
    carry = output[0]
    result = str( "%s%s", output[1],  result )
  }
  if ( carry == '1' ){
    result = str("1%s", result)
  }
  result // return 
}

println( bin_add('1101','1') )

- NoOne August 15, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * @author allwin.s
 */
public class BinarySum {

	public static void main(String[] args) {

		String s1 = "1";// "0000100";// "110";// "1011"; // "101";
		String s2 = "10";// "101";// "1000"; // "100";

		String res = "";
		res = add(s1.toCharArray(), s2.toCharArray(), s1.length() - 1, s2.length() - 1, 0, res);

		System.out.println(s1 + " + " + s2 + " = " + res);

	}

	private static String add(char[] A, char[] B, int i, int j, int carry, String result) {

		if (i < 0 && j < 0) {
			return (carry > 0 ? carry : "") + result;
		}

		int a = (i >= 0 ? A[i] - '0' : 0);
		int b = (j >= 0 ? B[j] - '0' : 0);
		int sum = a + b + carry;
		result = sum % 2 + result;

		return add(A, B, i - 1, j - 1, sum / 2, result);
	}
}

- Allwin S August 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* @Prashant
*/
const binaryAddition = (str1, str2) => {
if (!str1 && !str2) {
return '';
}
if (!str1) {
return str2;
} else if (!str2) {
return str1;
}


let result = '';

const limit = str1.length >= str2.length ? str1.length : str2.length;

let carry = '0';
for(let i = limit - 1; i >= 0; --i) {
let val1 = '';
if (i > (str1.length - 1)) {
val1 = '0';
} else {
val1 = str1[i];
}

let val2 = '';

if (i > (str2.length - 1)) {
val2 = '0';
} else {
val2 = str2[i];
}

if (val1 === '1' && val2 === '1' && carry === '0') {
result = '0' + result;
carry = '1';
} else if (val1 === '1' && val2 === '1' && carry === '1') {
result = '1' + result;
carry = '1';
} else if (val1 === '1' && val2 === '0' && carry === '0') {
result = '1' + result;
carry = '0';
} else if(val1 === '1' && val2 === '0' && carry === '1') {
result= '0' + result;
carry = '1';
} else if(val1 === '0' && val2 === '1' && carry === '0') {
result = '1' + result;
carry = '0';
} else if(val1 === '0' && val2 === '1' && carry === '1') {
result = '0' + result;
carry = '1';
} else if ((val1 === '0' && val2 === '0' && carry === '0') ) {
result = '0' + result;
carry = '0';
} else if ((val1 === '0' && val2 === '0' && carry === '1') ) {
result = '1' + result;
carry = '0';
}
}

if (carry === '1') {
result= '1' + result ;
}

return result;
}

- Prashant August 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		
		String first = "101";
		String second = "111";
		
		System.out.print("result: " + first + " + " + second);
		int plus = 0;
		ArrayList<String> res = new ArrayList<>();
		
		for (int i = first.length(); i > 0; i--) {
			
			int start = i - 1;
			int end = i;
			String firstSub = first.substring(start, end);
//			System.out.println(i + firstSub);
			
			String secondSub = second.substring(start, end);
//			System.out.println(i + secondSub);
			
			if (firstSub.equals(secondSub) && firstSub.equals("1")) {
				
				if (plus == 1) {
					res.add("1");
				} else {
					res.add("0");
				}
				
				plus = 1;
				
			} else if (firstSub.equals(secondSub) && firstSub.equals("0")) {
				
				if (plus == 1) {
					res.add("1");
				} else {
					res.add("0");
				}
				
				plus = 0;
				
			} else {
				
				if (plus == 1) {
					res.add("0");
					plus = 1;
				} else {
					res.add("1");
					plus = 0;
				}
			}
			
		}
		
		if (plus == 1) {
			res.add("1");
		}
		
		StringBuilder result = new StringBuilder();
		
		for (int i = (res.size() - 1); i >= 0; i--) {
			result.append(res.get(i));
		}
		
		System.out.print(" = " + result);
	}

- zgr.dmr August 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String add(String s1, String s2) {
        int len = Math.max(s1.length(), s2.length()) + 1;
        final StringBuilder result = new StringBuilder(len);

        int carryOver=0;
        int pos=0;

        for(int s1Iter = s1.length()-1, s2Iter = s2.length()-1; s1Iter>=0 || s2Iter>=0; s1Iter--, s2Iter--, pos++){
            final int s1Val = s1Iter >=0 ? s1.charAt(s1Iter)-'0': '0', s2Val = s2Iter >=0 ? s2.charAt(s2Iter)-'0' : '0';
            final int subsum = s1Val + s2Val + carryOver;

            result.append(subsum % 2);
            carryOver = subsum/2;
        }

        if(carryOver==1) result.append(carryOver);

        return reverse(result.toString());
    }

- Yev August 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is more space-efficient. Running time O(n).

public static String add(String s1, String s2) {
        int len = Math.max(s1.length(), s2.length()) + 1;
        final StringBuilder result = new StringBuilder(len);

        int carryOver=0;
 

        for(int s1Iter = s1.length()-1, s2Iter = s2.length()-1; s1Iter>=0 || s2Iter>=0; s1Iter--, s2Iter--){
            final int s1Val = s1Iter >=0 ? s1.charAt(s1Iter)-'0': '0', s2Val = s2Iter >=0 ? s2.charAt(s2Iter)-'0' : '0';
            final int subsum = s1Val + s2Val + carryOver;

            result.append(subsum % 2);
            carryOver = subsum/2;
        }

        if(carryOver==1) result.append(carryOver);

        return reverse(result.toString());
    }

- Yev August 25, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution, O(n) no type cast or conversion:

public static String add(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        char carry = '0';

        int i = s1.length() -1;
        int j = s2.length() -1;

        while(i >= 0 && j >= 0) {
            char a = s1.charAt(i);
            char b = s2.charAt(j);

            if (a == '0' && b == '0') {
                if (carry == '0') {
                    result.append("0");
                    carry = '0';
                }
                else {
                    result.append("1");
                    carry = '0';
                }
            }
            else if (a == '0' && b == '1' || a == '1' && b == '0') {
                if (carry == '0') {
                    result.append("1");
                    carry = '0';
                }
                else {
                    result.append("0");
                    carry = '1';
                }
            }
            else if (a == '1' && b == '1') {
                if (carry == '0') {
                    result.append("0");
                    carry = '1';
                }
                else {
                    result.append("1");
                    carry = '1';
                }
            }

            i--;
            j--;
        }

        while( i >= 0) {
            char a = s1.charAt(i);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            i--;
        }

        while(j >= 0) {
            char a = s2.charAt(j);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            j--;
        }

        if (carry == '1')
            result.append("1");

        return result.reverse().toString();
    }

- Freddy August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution, O(n) with no type conversion:

public static String add(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        char carry = '0';

        int i = s1.length() -1;
        int j = s2.length() -1;

        while(i >= 0 && j >= 0) {
            char a = s1.charAt(i);
            char b = s2.charAt(j);

            if (a == '0' && b == '0') {
                if (carry == '0') {
                    result.append("0");
                    carry = '0';
                }
                else {
                    result.append("1");
                    carry = '0';
                }
            }
            else if (a == '0' && b == '1' || a == '1' && b == '0') {
                if (carry == '0') {
                    result.append("1");
                    carry = '0';
                }
                else {
                    result.append("0");
                    carry = '1';
                }
            }
            else if (a == '1' && b == '1') {
                if (carry == '0') {
                    result.append("0");
                    carry = '1';
                }
                else {
                    result.append("1");
                    carry = '1';
                }
            }

            i--;
            j--;
        }

        while( i >= 0) {
            char a = s1.charAt(i);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            i--;
        }

        while(j >= 0) {
            char a = s2.charAt(j);

            if (a == '0' && carry == '0') {
                result.append("0");
            }
            else if (a == '0' && carry == '1' || a == '1' && carry == '0') {
                result.append("1");
                carry = '0';
            }
            else if (a == '1' && carry == '1') {
                result.append("0");
                carry = '1';
            }

            j--;
        }

        if (carry == '1')
            result.append("1");

        return result.reverse().toString();
    }

- Freddy August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function binaryAdd(numStr1, numStr2) {
    if (!numStr1) {
        return numStr2;
    } else if (!numStr2) {
        return numStr1;
    }
    
    let result = '';
    let longOne = numStr1.length >= numStr2.length ? numStr1 : numStr2;
    let shortOne = longOne === numStr1 ? numStr2 : numStr1;
    while (shortOne.length < longOne.length) {
        shortOne = '0' + shortOne;
    }
    let carry = 0;
    for (let i=longOne.length-1; i>=0; i--) {
        result  = ((parseInt(longOne[i]) + parseInt(shortOne[i]) + carry) % 2).toString() + result;
        carry = parseInt((parseInt(longOne[i]) + parseInt(shortOne[i]) + carry) / 2);
    }
    if (carry === 1) {
        result = '1' + result;
    }
    return result;
}

- Yoalnda August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def binary_add(s1, s2):
    if len(s1) != len(s2):
        #TODO: left pad with zeros
        raise
    # should probably check if all digits are '1' or '0'

    carryon = '0'
    i = len(s1) - 1
    res = ""
    while i >= 0:
        num_zeros = sum(map(lambda i: is_zero(i), [s1[i], s2[i], carryon]))
        if num_zeros > 1:
            carryon = "0"
        else:
            carryon = "1"

        if num_zeros == 0 or num_zeros == 2:
            res = "1" + res
        else:
            res = "0" + res
        i = i - 1
    if carryon != "0":
        return "1" + res
    return res

- Rachel August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Bute Force: Iterate over each pair of numbers and add them O(S1 + S2 + (MaxSize(S1, S2) + 1)) => O(MaxSize(S1,S2))
 * Pointer starts from last char and go over the string (index as a pointer)
 * And save carry value to be added in the next iteration
 * If I reach the end o the string and I still a carried value a need to add them to the final
 * That way the length of the result could be bigger than string
 * So, I need to reverse the string in the end
 * 
 * Optimization: I can compute the size of the small until I have a carried value, after that copy the last of bigger string
 * I can optimize my space, doing the sum in place, i.e., I can use the bigger string O(S1+2)
 * 
 */

function sum(s1, s2) {

  let p2 = s2.size - 1;
  let p1 = s1.size - 1;

  if (p1 > p2) {
    return add(s2, s1, p2, p1, 0);
  }
  return add(s1, s2, p1, p2, 0);
}

function add(s1, s2, p1, p2, carried) {
  if (p1 < 0  && carried === 0) {
    return s2;
  }
  const result = addNumber(s1[p1], s2[p2], carried);
  s2[p2] = result.value;

  add(s1, s2, p1--, p2--, result.carried);
}

/*
* 1 + 1 + 1 = 1 1
  1 + 0 + 1 = 0 1
  0 + 0 + 1 = 1 0
*/

function addNumber(char1=0, char2, c) {
  let value = 0;
  let carried = 0;
  const n1 = Number(char1);
  const n2 = Number(char2);
  if (n1 === 1 && n2 === 1) {
    value = c;
    carried = 1;
  }
  else if (n1 !== n2) {
    value = c === 1 ? 0 : 1;
  } else {
    value = c;
  }
  return {
    value,
    carried
  }
}

- Keilla September 05, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Brute force: Iterate over each pair of numbers and add them O(S1 + S2 + (MaxSize(S1, S2) + 1)) => O(MaxSize(S1,S2))
 * Pointer starts from last char and go over the string (index as a pointer)
 * And save carry value to be added in the next iteration
 * If I reach the end o the string and I still a carried value a need to add them to the final
 * That way the length of the result could be bigger than string
 * So, I need to reverse the string in the end
 * 
 * Optimization: I can compute the size of the small until I have a carried value, after that copy the last of bigger string
 * I can optimize my space, doing the sum in place, i.e., I can use the bigger string O(S1+2)
 * 
 */

function sum(s1, s2) {

  let p2 = s2.size - 1;
  let p1 = s1.size - 1;

  if (p1 > p2) {
    return add(s2, s1, p2, p1, 0);
  }
  return add(s1, s2, p1, p2, 0);
}

function add(s1, s2, p1, p2, carried) {
  if (p1 < 0  && carried === 0) {
    return s2;
  }
  const result = addNumber(s1[p1], s2[p2], carried);
  s2[p2] = result.value;

  add(s1, s2, p1--, p2--, result.carried);
}

/*
* 1 + 1 + 1 = 1 1
  1 + 0 + 1 = 0 1
  0 + 0 + 1 = 1 0
*/

function addNumber(char1=0, char2, c) {
  let value = 0;
  let carried = 0;
  const n1 = Number(char1);
  const n2 = Number(char2);
  if (n1 === 1 && n2 === 1) {
    value = c;
    carried = 1;
  }
  else if (n1 !== n2) {
    value = c === 1 ? 0 : 1;
  } else {
    value = c;
  }
  return {
    value,
    carried
  }
}

- keilla September 05, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# PYTHON PROGRAM

binary1 = "101101"
binary2 = "111011"
binary_sum = []

# Use a dictionary with all possible addends
# and their sum and remainders
# key = "prev_remainder, b1, b2"
# value = "curr_remainder, curr_sum"
d = {}
d['0','0','0'] = ['0','0']
d['0','0','1'] = ['0','1']
d['0','1','0'] = ['0','1']
d['0','1','1'] = ['1','0']

d['1','0','0'] = ['0','1']
d['1','0','1'] = ['1','0']
d['1','1','0'] = ['1','0']
d['1','1','1'] = ['1','1']

prev_remainder = '0'
for b1, b2 in zip(binary1, binary2):
curr_remainder, curr_sum = d[prev_remainder,b1,b2]
binary_sum.append(curr_sum)
prev_remainder = curr_remainder

binary_sum.append(prev_remainder)
binary_sum.reverse()
print(''.join(map(str,binary_sum)))

- Naveen September 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Implementation using Dictionary:

binary1 = "101101"
binary2 = "111011"
binary_sum = []

# Use a dictionary with key = addends and 
# values as remainder and sum
# key = "prev_remainder, b1, b2"
# value = "curr_remainder, curr_sum"
d = {}
d['0','0','0'] = ['0','0']
d['0','0','1'] = ['0','1']
d['0','1','0'] = ['0','1']
d['0','1','1'] = ['1','0']

d['1','0','0'] = ['0','1']
d['1','0','1'] = ['1','0']
d['1','1','0'] = ['1','0']
d['1','1','1'] = ['1','1']

prev_remainder = '0'
for b1, b2 in zip(binary1, binary2):
    curr_remainder, curr_sum = d[prev_remainder,b1,b2]
    binary_sum.append(curr_sum)
    prev_remainder = curr_remainder

binary_sum.append(prev_remainder)
binary_sum.reverse()
print(''.join(map(str,binary_sum)))

- Naveen September 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const numberOne = '11';
const numberTwo = '11';

function sumBin(num1, num2, position1, position2, carry = 0) {

    if(position1 < 0 && position2 < 0) {
        return carry > 0 ? carry : '';
    }
    const bin1 = num1.charAt(position1) - 0;
    const bin2 = num2.charAt(position2) - 0;
    const sum = bin1 + bin2 + carry;
    const result = sum % 2;

    return sumBin(num1, num2, position1 - 1, position2 - 1, sum > 1 ? 1 : 0) + `${result}`;
}

const result = sumBin(numberOne, numberTwo, numberOne.length - 1, numberTwo.length - 1);

- Dorin September 10, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String calculate(String a, String b) {
		int aLen = a.length();
		int bLen = b.length();
		if(aLen < bLen) {
			int diffCount = bLen - aLen;
			a = "0".repeat(diffCount) + a;
		} else if(aLen > bLen) {
			int diffCount = aLen - bLen;
			b = "0".repeat(diffCount) + b;
		}

		Stack<String> xNum = new Stack<>();
		Stack<String> yNum = new Stack<>();
		for (char c : a.toCharArray()) {
			xNum.add(String.valueOf(c));
		}
		for (char c : b.toCharArray()) {
			yNum.add(String.valueOf(c));
		}

		return result = add("", xNum, yNum, "0");
	}

public String add(String result, Stack<String> num1, Stack<String> num2, String carry) {
		if(num1.isEmpty()) {
			return result + carry;
		}
		String bit1 = num1.pop();
		String bit2 = num2.pop();
		long numberOfOnes = (bit1 + bit2 + carry).chars().filter(c -> c == '1').count();
		String newCarry = null;
		String tempResult = null;
		if(numberOfOnes == 0) {
			newCarry = "0";
			tempResult = "0";
		} else if(numberOfOnes == 1) {
			newCarry = "0";
			tempResult = "1";
		} else if(numberOfOnes == 2) {
			newCarry = "1";
			tempResult = "0";
		} else if(numberOfOnes == 3) {
			newCarry = "1";
			tempResult = "1";
		}
		return add(tempResult, num1, num2, newCarry) + result;
	}

- esoner.sezgin September 13, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <algorithm>

std::string bsum(std::string str1, std::string str2) {
    
    std::string result;
    
    int acc =  0;
    auto it1 = str1.rbegin();
    auto it2 = str2.rbegin();
    
    for (; it1 != str1.rend() && it2 != str2.rend(); it1++, it2++) {
        if (*it1 == *it2) {
            if (*it1 == '1') {
                (acc == 0) ? result.push_back('0') : result.push_back('1');
                acc = 1;
            }
            else {
                (acc == 1) ? result.push_back('1') : result.push_back('0');
                acc = 0;
            }
        }
        else {
            if (*it1 != *it2) {
                if (acc == 1) {
                    result.push_back('0');
                    acc = 1;
                }
                else {
                    result.push_back('1');
                    acc = 0;
                }
            }
        }
    }
    
    if (it1 != str1.rend()) {
        while (it1 != str1.rend()) {
            if (*it1 == '1') {
                (acc == 0) ? result.push_back('1') : result.push_back('0');
            }
            else {
                (acc == 0) ? result.push_back('0') : result.push_back('1');
                acc = 0;
            }
            it1++;
        }
    }
    else {
        if (it2 != str2.rend()) {
            while (it2 != str2.rend()) {
                if (*it2 == '1') {
                    (acc == 0) ? result.push_back('1') : result.push_back('0');
                }
                else {
                    (acc == 0) ? result.push_back('0') : result.push_back('1');
                    acc = 0;
                }
                it2++;
            }
        }
    }
    
    if (acc) {
        result.push_back('1');
    }
  
    std::reverse(result.begin(), result.end());
  
    return result;
}

- arturocu81 October 11, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function sum(a, b, carry) {
    const aN = a === '0' ? 0 : 1;
    const bN = b === '0' ? 0 : 1;
    return aN + bN + carry;
}

function addBinary(A, B) {
    let result = '';
    let aIdx = A.length -1;
    let bIdx = B.length -1;
    let carry = 0;
    while (aIdx >=0 || bIdx >=0) {
        const aDigit = aIdx >=0 ? A[aIdx] : '0';
        const bDigit = bIdx >=0 ? B[bIdx] : '0';
        aIdx--;
        bIdx--;
        const total = sum(aDigit, bDigit, carry);
        const digit = (total%2 === 0) ? 0 : 1;
        carry = (total>1) ? 1 : 0;
        
        result = digit + result;
    }
    if (carry) result = carry + result;
    return result;
}

- Pablo October 19, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// /*
// * implement binary additions of two strings
// * s1 = "1010011"
// * s2 = " 101"
// */


char add_char (char c1, char c2, char *c) {
int c1N = c1 == '0' ? 0 : 1;
int c2N = c2 == '0' ? 0 : 1;
int carryN = *c == '0' ? 0 : 1;
char sum = (c1N + c2N + carryN)%2 ? '1' : '0';

*c = (c1N + c2N + carryN)/2 ? '1' : '0';
return sum;

}

char * add_binary (char *s1, char *s2)
{
char * result = NULL;
int l1 = strlen(s1);
int l2 = strlen(s2);
int len;
if (l1 == 0)
return s2;

if (l2 == 0)
return s1;

if (l1 >= l2) {
result = calloc(l1, sizeof(char));
len = l1;
} else {
result = calloc(l2, sizeof(char));
len = l2;
}

if (result == NULL)
return NULL;

char carry = '0';
int index1 = strlen(s1);
int index2 = strlen(s2);
int rindex = len;

while (rindex > 0) {
result[--rindex] = add_char(
(index1 > 0) ? s1[--index1] : '0',
(index2 > 0) ? s2[--index2] : '0',
&carry);
}

return result;

}


int main(void)
{
char * result = add_binary("1010011", "101");
printf("%s\n", result);
free(result);
return 0;
}

- Anonymous October 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
public static void main(String[] args) {
System.out.println(add("01", "1101"));
}

public static String add(String s1, String s2) {
StringBuilder result = new StringBuilder();
char carry = '0';

int i = s1.length() -1;
int j = s2.length() -1;

if(i > j)
{
int diff = i-j;
int x =0;
for(x=0; x<diff; x++){
s2 = '0' + s2;
}
}else{
int diff = j-i;
int x =0;
for(x=0; x<diff; x++){
s1 = '0' + s1;
}
}
System.out.println("s1: " + s1 +"\n");
System.out.println("s2: " + s2 +"\n");

i = s1.length() -1;
j = s2.length() -1;

while(i >= 0 && j >= 0) {
char a = s1.charAt(i);
char b = s2.charAt(j);

if (a == '0' && b == '0') {
if (carry == '0') {
result.append("0");
carry = '0';
}
else {
result.append("1");
carry = '0';
}
}
else if (a == '0' && b == '1' || a == '1' && b == '0') {
if (carry == '0') {
result.append("1");
carry = '0';
}
else {
result.append("0");
carry = '1';
}
}
else if (a == '1' && b == '1') {
if (carry == '0') {
result.append("0");
carry = '1';
}
else {
result.append("1");
carry = '1';
}
}

i--;
j--;

System.out.println("result: " + result +"\n");
}

if(carry !='0')
return '1' + result.reverse().toString();
else
return result.reverse().toString();
}
}

- AJ October 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
  public static void main(String[] args) {
    System.out.println(add("01", "1101"));
  }
  
  public static String add(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        char carry = '0';

        int i = s1.length() -1;
        int j = s2.length() -1;
    
        if(i > j)
        {
          int diff = i-j;
          int x =0;
          for(x=0; x<diff; x++){
            s2 = '0' + s2;
          }
        }else{
          int diff = j-i;
          int x =0;
          for(x=0; x<diff; x++){
            s1 = '0' + s1;
          }
        }
        System.out.println("s1: " + s1 +"\n");
        System.out.println("s2: " + s2 +"\n");
    
        i = s1.length() -1;
        j = s2.length() -1;

        while(i >= 0 && j >= 0) {
            char a = s1.charAt(i);
            char b = s2.charAt(j);

            if (a == '0' && b == '0') {
                if (carry == '0') {
                    result.append("0");
                    carry = '0';
                }
                else {
                    result.append("1");
                    carry = '0';
                }
            }
            else if (a == '0' && b == '1' || a == '1' && b == '0') {
                if (carry == '0') {
                    result.append("1");
                    carry = '0';
                }
                else {
                    result.append("0");
                    carry = '1';
                }
            }
            else if (a == '1' && b == '1') {
                if (carry == '0') {
                    result.append("0");
                    carry = '1';
                }
                else {
                    result.append("1");
                    carry = '1';
                }
            }

            i--;
            j--;
          
          System.out.println("result: " + result +"\n");
        }
    
        if(carry !='0')
          return '1' + result.reverse().toString();
        else
          return result.reverse().toString();
    }
}

- AJ October 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n1="101101"
n2="111101"
n3=""
i=len(n1)
c=0
while i>=0:
    if (n1[i-1]=="0" and n2[i-1]=="0" and c==0): #0
        c=0
        n3="0" +n3
    elif (n1[i-1]=="1" and n2[i-1]=="0" and c==0) or (n1[i-1]=="0" and n2[i-1]=="1" and c==0) or (n1[i-1]=="0" and n2[i-1]=="0" and c==1):#1
        n3="1"+n3
        c=0
    if (n1[i-1]=="1" and n2[i-1]=="1" and c==0) or (n1[i-1]=="1" and n2[i-1]=="0" and c==1) or (n1[i-1]=="0" and n2[i-1]=="1" and c==1):#2
        c=1
        n3="0"+n3
    elif (n1[i-1]=="1" and n2[i-1]=="1" and c==1):#3
        c=1
        n3="1"+n3
    i=i-1

print(n3)

- Alok October 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from itertools import zip_longest

def add(a, b):
    def gen_add():
        c = 0
        for i, j in zip_longest(reversed(a), reversed(b), fillvalue='0'):
            n = (ord(i) - ord('0')) + (ord(j) - ord('0')) + c
            yield chr(ord('0') + n % 2)
            c = n // 2
        if c:
            yield chr(ord('0') + c)
    
    return ''.join(reversed(list(gen_add())))

print(add('101101', '111101'))

- ne0 October 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript

var addBinary = function(a, b) {
     var loop = Math.max(a.length, b.length)
     var carry = 0
     let result = []
     let arrA = a.split('')
     let arrB = b.split('')
    for (var i = 0 ; i <= loop ; i++)  {
        const pos = parseInt(arrA.pop() || 0) + parseInt(arrB.pop() || 0) + carry
        carry = pos >= 2 ? 1 : 0
        if (pos === 1 || pos === 3) {
          result.unshift(1)
        } else if (pos === 2 || (pos === 0 && (i < loop - 1))) {
          result.unshift(0)
        }
    }
    return result.join('') || '0'
};

- rwu October 30, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const helperObject = {
    0: [0, 0],
    1: [1, 0],
    2: [0, 1],
    3: [1, 1]
};
function sumBinary(str1, str2) {
    //todo: edge cases
    let maxLength = Math.max(str1.length, str2.length);
    let result = '';
    let carry = '';

    for (let i = 0; i < maxLength; i++) {
        const sum = +(str1[str1.length - i - 1] ?? 0) + +(str2[str2.length - i - 1] ?? 0) + carry;
        let newChar = '';
        [newChar, carry] = helperObject[sum];
        result = newChar + result;
    }
    return carry === 1 ? carry + result : result;
}

- Mehrdad November 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const helperObject = {
    0: [0, 0],
    1: [1, 0],
    2: [0, 1],
    3: [1, 1]
};
function sumBinary(str1, str2) {
    const len1 = str1.length;
    const len2 = str2.length
    let maxLength = Math.max(len1, len2);
    let result = '';
    let carry = '';

    for (let i = 0; i < maxLength; i++) {
        const sum = +(str1[len1 - i - 1] ?? 0) + +(str2[len2 - i - 1] ?? 0) + carry;
        let newChar = '';
        [newChar, carry] = helperObject[sum];
        result = newChar + result;
    }
    return carry === 1 ? carry + result : result;
}

- Mehrdad November 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

char add_char(char x, char y, char z, bool* carry) {
*carry = false;
if (x == '0' && y == '0') {
return z;
}
if (y == '0' && z == '0') {
return x;
}
if (x == '0' && z == '0') {
return y;
}
*carry = true;
if (x == '1' && y == '1' && z == '1') {
return '1';
}
return '0';
}


string add_binary(string x, string y) {
string longer = (x.size() > y.size()) ? x : y;
string shorter = (x.size() > y.size()) ? y : x;
int i = longer.size() - 1;
int j = shorter.size() - 1;
bool carry = false;
string ret = "";
for (; j >= 0; i--, j--) {
char c = add_char(longer[i], shorter[j], (carry) ? '1' : '0', &carry);
ret.insert(0, string(1, c));
}
for (; i >= 0; i--) {
char c = add_char(longer[i], '0', (carry) ? '1' : '0', &carry);
ret.insert(0, string(1, c));
}
if (carry) ret.insert(0, "1");
return ret;
}

int main()
{
cout << add_binary("101101", "111101");
return 0;
}

- Jacob December 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

char add_char(char x, char y, char z, bool* carry) {
*carry = false;
if (x == '0' && y == '0') {
return z;
}
if (y == '0' && z == '0') {
return x;
}
if (x == '0' && z == '0') {
return y;
}
*carry = true;
if (x == '1' && y == '1' && z == '1') {
return '1';
}
return '0';
}


string add_binary(string x, string y) {
string longer = (x.size() > y.size()) ? x : y;
string shorter = (x.size() > y.size()) ? y : x;
int i = longer.size() - 1;
int j = shorter.size() - 1;
bool carry = false;
string ret = "";
for (; j >= 0; i--, j--) {
char c = add_char(longer[i], shorter[j], (carry) ? '1' : '0', &carry);
ret.insert(0, string(1, c));
}
for (; i >= 0; i--) {
char c = add_char(longer[i], '0', (carry) ? '1' : '0', &carry);
ret.insert(0, string(1, c));
}
if (carry) ret.insert(0, "1");
return ret;
}

int main()
{
cout << add_binary("101101", "111101");
return 0;
}

- Jacob December 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ implementation:

#include <iostream>

using namespace std;

char add_char(char x, char y, char z, bool* carry) {
    *carry = false;
    if (x == '0' && y == '0') {
        return z;
    }
    if (y == '0' && z == '0') {
        return x;
    }
    if (x == '0' && z == '0') {
        return y;
    }
    *carry = true;
    if (x == '1' && y == '1' && z == '1') {
        return '1';
    }
    return '0';
}


string add_binary(string x, string y) {
    string longer = (x.size() > y.size()) ? x : y;
    string shorter = (x.size() > y.size()) ? y : x;
    int i = longer.size() - 1;
    int j = shorter.size() - 1;
    bool carry = false;
    string ret = "";
    for (; j >= 0; i--, j--) {
        char c = add_char(longer[i], shorter[j], (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    for (; i >= 0; i--) {
        char c = add_char(longer[i], '0', (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    if (carry) ret.insert(0, "1");
    return ret;
}

int main()
{
    cout << add_binary("101101", "111101");
    return 0;
}

- Jacob December 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

char add_char(char x, char y, char z, bool* carry) {
    *carry = false;
    if (x == '0' && y == '0') {
        return z;
    }
    if (y == '0' && z == '0') {
        return x;
    }
    if (x == '0' && z == '0') {
        return y;
    }
    *carry = true;
    if (x == '1' && y == '1' && z == '1') {
        return '1';
    }
    return '0';
}


string add_binary(string x, string y) {
    string longer = (x.size() > y.size()) ? x : y;
    string shorter = (x.size() > y.size()) ? y : x;
    int i = longer.size() - 1;
    int j = shorter.size() - 1;
    bool carry = false;
    string ret = "";
    for (; j >= 0; i--, j--) {
        char c = add_char(longer[i], shorter[j], (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    for (; i >= 0; i--) {
        char c = add_char(longer[i], '0', (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    if (carry) ret.insert(0, "1");
    return ret;
}

int main()
{
    cout << add_binary("101101", "111101");
    return 0;
}

- Jacob December 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

char add_char(char x, char y, char z, bool* carry) {
    *carry = false;
    if (x == '0' && y == '0') {
        return z;
    }
    if (y == '0' && z == '0') {
        return x;
    }
    if (x == '0' && z == '0') {
        return y;
    }
    *carry = true;
    if (x == '1' && y == '1' && z == '1') {
        return '1';
    }
    return '0';
}


string add_binary(string x, string y) {
    string longer = (x.size() > y.size()) ? x : y;
    string shorter = (x.size() > y.size()) ? y : x;
    int i = longer.size() - 1;
    int j = shorter.size() - 1;
    bool carry = false;
    string ret = "";
    for (; j >= 0; i--, j--) {
        char c = add_char(longer[i], shorter[j], (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    for (; i >= 0; i--) {
        char c = add_char(longer[i], '0', (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    if (carry) ret.insert(0, "1");
    return ret;
}

int main()
{
    cout << add_binary("101101", "111101");
    return 0;
}

- Anonymous December 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

char add_char(char x, char y, char z, bool* carry) {
    *carry = false;
    if (x == '0' && y == '0') {
        return z;
    }
    if (y == '0' && z == '0') {
        return x;
    }
    if (x == '0' && z == '0') {
        return y;
    }
    *carry = true;
    if (x == '1' && y == '1' && z == '1') {
        return '1';
    }
    return '0';
}


string add_binary(string x, string y) {
    string longer = (x.size() > y.size()) ? x : y;
    string shorter = (x.size() > y.size()) ? y : x;
    int i = longer.size() - 1;
    int j = shorter.size() - 1;
    bool carry = false;
    string ret = "";
    for (; j >= 0; i--, j--) {
        char c = add_char(longer[i], shorter[j], (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    for (; i >= 0; i--) {
        char c = add_char(longer[i], '0', (carry) ? '1' : '0', &carry);
        ret.insert(0, string(1, c));
    }
    if (carry) ret.insert(0, "1");
    return ret;
}

int main()
{
    cout << add_binary("101101", "111101");
    return 0;
}

- Jacob December 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm going to use Node.js to write the algorithm.

My approach is to transform both strings in an array of characters and iterate over each element of both arrays to calculate the result and the eventual carry.

Assumptions:
- Strings must be a sequence of 0 and 1 symbols
- Both strings must have the same length (for simplification)
- The character "0" is mapped to false, while "1" to true
- The implicit type coercion in JavaScript will map "0" and "1" as truthy/falsay values
- I'm using the XOR operator to do the sum, and the AND to calculate the carry
- I'm appending the overflow at the end if any

If x, y and c are respectively the first number, second number and the carry
- x ^ y ^ c => gives the result
- x & y || x & c || y & c => gives the carry

This is my solution

// input
const a = '10101010';
const b = '00100011';
const length = 8;

// aux variables
const result = Array(length);
let carry = 0;

// transform the strings to array of chars
const x = a.split('');
const y = b.split('');

for (let i = length - 1; i >= 0; i--) {
  result[i] = x[i] ^ y[i] ^ carry;
  carry = x[i] & y[i] || x[i] & carry || y[i] & carry
}

const overflow = carry;
const finalResult = overflow ? `${overflow}${result}` : `${result.join('')}`;

console.log(`${a} + ${b} = ${finalResult}`);

- Simone Spaccarotella January 20, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used Node.js to code the solution

Assumptions:
- The two strings have the same size (for simplicity). If they weren't, I would have padded the smaller number with zeros;
- The strings are made by 0 and 1 only;
- The symbol "0" is mapped as false, and "1" as true;

Approach:
- Transform both strings in array of characters
- Initialise the carry to "0"
- Scan the array and calculate the sum for between the elements of the two array plus the carry
- The sum is calculated using the XOR operator, while the carry using the AND operator.
- The implicit type coercion in JavaScript allows me to map strings to truthy/falsey values and calculate sum and carry with the boolean operators

Complexity
- O(n) in time and space

// input
const a = '10101010';
const b = '00100011';
const length = 8;

// aux variables
const result = Array(length);
let carry = 0;

// transform the strings to array of chars
const x = a.split('');
const y = b.split('');

for (let i = length - 1; i >= 0; i--) {
  result[i] = x[i] ^ y[i] ^ carry;
  carry = x[i] & y[i] || x[i] & carry || y[i] & carry
}

const overflow = carry;
const finalResult = overflow ? `${overflow}${result}` : `${result.join('')}`;

console.log(`${a} + ${b} = ${finalResult}`);

- Simone Spaccarotella January 20, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) operation, being N === max(len(s1), len(s2))

const assert = require("assert").strict;

function binSum(s1, s2) {
  let res = "";
  const [big, small] = s1.length > s2.length ? [s1, s2] : [s2, s1];

  /**
   * @typedef result "0" | "1"
   * @typedef acc "0" | "1"
   * @type {Record<string, [result, acc]>}
   */
  const operations = {
    "000": ["0", "0"],
    "001": ["1", "0"],
    "010": ["1", "0"],
    "100": ["1", "0"],
    "011": ["0", "1"],
    "101": ["0", "1"],
    "110": ["0", "1"],
    "111": ["1", "1"],
  };

  let acc = "0";
  for (let i = big.length - 1; i >= 0; i--) {
    const smallCurr = small[i] || '0';
    const idx = `${big[i]}${smallCurr}${acc}`;

    let op = operations[idx];
    res = op[0] + res;
    acc = op[1];
  }

  return acc === '1' ? '1' + res : res;
}

assert.equal(binSum("101101", "111101"), "1101010");

- Rubens January 23, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) runtime/space complexity, being N === max(len(s1), len(s2))

const assert = require("assert").strict;

function binSum(s1, s2) {
  let res = "";
  const [big, small] = s1.length > s2.length ? [s1, s2] : [s2, s1];

  /**
   * @typedef result "0" | "1"
   * @typedef acc "0" | "1"
   * @type {Record<string, [result, acc]>}
   */
  const operations = {
    "000": ["0", "0"],
    "001": ["1", "0"],
    "010": ["1", "0"],
    "100": ["1", "0"],
    "011": ["0", "1"],
    "101": ["0", "1"],
    "110": ["0", "1"],
    "111": ["1", "1"],
  };

  let acc = "0";
  for (let i = big.length - 1; i >= 0; i--) {
    const smallCurr = small[i] || '0';
    const idx = `${big[i]}${smallCurr}${acc}`;

    let op = operations[idx];
    res = op[0] + res;
    acc = op[1];
  }

  return acc === '1' ? '1' + res : res;
}

assert.equal(binSum("101101", "111101"), "1101010");

- rubenspgcavalcante January 23, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

>>>a='101101'
>>>b='111101'
>>>sum = a[0],b[1],a[1],b[2],a[1],b[0],b[4]
>>> ' '.join(sum)
'1101010'

- psico.eyanez February 24, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function binarySum(s1,s2) {
let ans = "";
let buff = 0;
const length = Math.max(s1.length, s2.length);
const padding = (s, length) => (length - s.length) > 0 ? "0".repeat(length - s.length) + s : s;

s1 = padding(s1, length);
s2 = padding(s2, length);

for (let i = length - 1; i >= 0; i--) {
ans = (s1[i] ^ s2[i] ^ buff) + ans;
buff = (s1[i] | buff) & s2[i] | (s2[i] | buff) & s1[i];
}

if (buff) ans = buff + ans;

return ans;
}

- pacendrix March 13, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Implement binary addition of two strings.
// For example "101101" and "111101" equal "1101010"
// You cannot use any type conversion, operate only with strings.

// "1" + "0" = "1"
// "0" + "0" = "0"
// "1" + "1" = "0" reminder-1
//
// "1" + "0" + reminder-1 = "0" reminder-1
// "1" + "1" + reminder-1 = "1" reminder-1
// "0" + "0" + reminder-1 = "1"
//
// first + second = (first(0..n-1) + second(0..m-1) + reminder(first(n) + second(m)) append (first(n) + second(m))
//
// "101101" +  "111101" = ("10110" + "11110" + reminder-1) append 0

func StringBinaryAdd(first string, second string) string {
	return StringBinaryAddRecursive(first, second, "0")
}

func StringBinaryAddRecursive(first string, second string, currentReminder string) string {
  if len(first) == 0 && len(second) == 0 {
    if currentReminder == "1" {
      return "1"
    }
    return ""
  }
  if len(first) == 0 {
     return StringBinaryAddRecursive(second, currentReminder, "0")
  }

  if len(second) == 0 {
     return StringBinaryAddRecursive(first, currentReminder, "0")
  }
  
  lastFirstIndex := len(first)-1
  lastSecondIndex := len(second)-1

  result, lastIndexReminder := addBinaryStringSingleDigit(string(first[lastFirstIndex]), string(second[lastSecondIndex]))
  result, tempReminder := addBinaryStringSingleDigit(result, currentReminder)
  finalReminder, _ := addBinaryStringSingleDigit(lastIndexReminder, tempReminder)
  return StringBinaryAddRecursive(first[:lastFirstIndex], second[:lastSecondIndex], finalReminder) + result 
}


func addBinaryStringSingleDigit(firstDigit string, secondDigit string) (result string, reminder string) {
   if firstDigit == "0" {
      if secondDigit == "0" {
          return "0", "0"    
      }
      return "1", "0"
   } else {
     if secondDigit == "0" {
          return "1", "0"
     }
     return "0", "1"
   }
}

- xuannhat25 March 17, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

add_rules = {
    ('0', '0', '0'): ('0', '0'),
    ('0', '0', '1'): ('0', '1'),
    ('0', '1', '0'): ('0', '1'),
    ('0', '1', '1'): ('1', '0'),
    ('1', '0', '0'): ('0', '1'),
    ('1', '0', '1'): ('1', '0'),
    ('1', '1', '0'): ('1', '0'),
    ('1', '1', '1'): ('1', '1'),
}


def add_binary_strings(l: str, r: str) -> str:
    result = []
    c = '0'

    l1 = list(l)
    l1.reverse()
    r1 = list(r)
    r1.reverse()

    # Pad both list with '0' to the same length
    while len(l1) < len(r1):
        l1.append('0'),

    while len(r1) < len(l1):
        r1.append('0')

    for a, b in zip(l1, r1):
        c, v = add_rules[(c, a, b)]
        result.append(v)

    if c == '1':
        result.append(c)

    result.reverse()
    return "".join(result)

- Vassili Gorshkov April 09, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

add_rules = {
    ('0', '0', '0'): ('0', '0'),
    ('0', '0', '1'): ('0', '1'),
    ('0', '1', '0'): ('0', '1'),
    ('0', '1', '1'): ('1', '0'),
    ('1', '0', '0'): ('0', '1'),
    ('1', '0', '1'): ('1', '0'),
    ('1', '1', '0'): ('1', '0'),
    ('1', '1', '1'): ('1', '1'),
}


def add_binary_strings(l: str, r: str) -> str:
    result = []
    c = '0'

    l1 = list(reversed(list(l)))
    r1 = r[::-1]

    # Pad both list with '0' to the same length
    while len(l1) < len(r1):
        l1.append('0'),

    while len(r1) < len(l1):
        r1.append('0')

    for a, b in zip(l1, r1):
        c, v = add_rules[(c, a, b)]
        result.append(v)

    if c == '1':
        result.append(c)

    result.reverse()
    return "".join(result)


print(add_binary_strings("101101", "1101010") == "10010111")

- Vassili Gorshkov April 10, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just for the fun of it, implement like a binary circuit with half and full adders

public final class BinaryCircuit
{
    private final static char ZeroBit   = '0';
    private final static char OneBit    = '1';
    private final static char AndTab[]  = { ZeroBit, ZeroBit, OneBit  };
    private final static char OrTab[]   = { ZeroBit, OneBit,  OneBit  };
    private final static char XorTab[]  = { ZeroBit, OneBit,  ZeroBit };
    
    public final class Adder
    {
        public Adder(char s, char c)
        {
            this.s = s;
            this.c = c;
        }
        
        public final char s;
        public final char c;
    }
    
    public static void Test()
    {
        BinaryCircuit circuit = new BinaryCircuit();
        
        circuit.TestAdd();
    }
   
    public final String Add(String x, String y)
    {
        int m = x.length();
        int n = y.length();
        
        int depth = Math.max(m, n);
        
        char[] sum = new char[depth+1];
        
        int i = depth;
        int j = m-1;
        int k = n-1;
        
        char carry = ZeroBit;
        
        while(i > 0)
        {
            char a = Digit(x, j--);
            char b = Digit(y, k--);
            
            Adder adder = FullAdder(a, b, carry);
            
            sum[i] = adder.s;
            carry  = adder.c;
            
            i--;
        }
        
        if (carry == OneBit)
        {
            sum[0] = carry;
        }
        
        return new String(sum).trim();
    }
    
    private Adder HalfAdder(
        char a, 
        char b
        )
    {
        return new Adder(BitXor(a, b), BitAnd(a, b));
    }
    
    private Adder FullAdder(
        char a, 
        char b, 
        char c
        )
    {
        Adder adder1 = HalfAdder(a, b);
        Adder adder2 = HalfAdder(adder1.s, c);
        char  carry  = BitOr(adder1.c, adder2.c);
        
        return new Adder(adder2.s, carry);
    }
    
    private static char BitAnd(char x, char y)
    {
        return AndTab[Index(x, y)];
    }
    
    private static char BitOr(char x, char y)
    {
        return OrTab[Index(x, y)];
    }
    
    private static char BitXor(char x, char y)
    {
        return XorTab[Index(x, y)];
    }
   
    private static int Index(char x, char y)
    {
        return (x - ZeroBit) + (y - ZeroBit);
    }
    
    private static char Digit(String x, int i)
    {
        return i >= 0 && i < x.length() ?  x.charAt(i) : ZeroBit;
    }
    
    private void TestAdd()
    {
        Eval("0", "0", "0");
        Eval("0", "1", "1");
        Eval("1", "0", "1");
        Eval("1", "1", "10");
        Eval("111", "10", "1001");
        Eval("1111", "110", "10101");
        Eval("11", "1", "100");
        Eval("1111", "1111", "11110");
        Eval("10000", "10000", "100000");
    }
    
    private void Eval(String x, String y, String r)
    {
        String z = Add(x, y);
        
        System.out.printf("X[%s] + Y[%s] = Z[%s]\n", x, y, z);
        
        if (z.equalsIgnoreCase(r) == false)
        {
            throw new RuntimeException(
                "Computed result NOT EQUAL to expected result"
                );
        }
    }
}

- Ray Patch April 13, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public final class BinaryCircuit
{
    private final static char ZeroBit   = '0';
    private final static char OneBit    = '1';
    private final static char AndTab[]  = { ZeroBit, ZeroBit, OneBit  };
    private final static char OrTab[]   = { ZeroBit, OneBit,  OneBit  };
    private final static char XorTab[]  = { ZeroBit, OneBit,  ZeroBit };
    
    public final class Adder
    {
        public Adder(char s, char c)
        {
            this.s = s;
            this.c = c;
        }
        
        public final char s;
        public final char c;
    }
    
    public static void Test()
    {
        BinaryCircuit circuit = new BinaryCircuit();
        
        circuit.TestAdd();
    }
   
    public final String Add(String x, String y)
    {
        int m = x.length();
        int n = y.length();
        
        int depth = Math.max(m, n);
        
        char[] sum = new char[depth+1];
        
        int i = depth;
        int j = m-1;
        int k = n-1;
        
        char carry = ZeroBit;
        
        while(i > 0)
        {
            char a = Digit(x, j--);
            char b = Digit(y, k--);
            
            Adder adder = FullAdder(a, b, carry);
            
            sum[i] = adder.s;
            carry  = adder.c;
            
            i--;
        }
        
        if (carry == OneBit)
        {
            sum[0] = carry;
        }
        
        return new String(sum).trim();
    }
    
    private Adder HalfAdder(
        char a, 
        char b
        )
    {
        return new Adder(BitXor(a, b), BitAnd(a, b));
    }
    
    private Adder FullAdder(
        char a, 
        char b, 
        char c
        )
    {
        Adder adder1 = HalfAdder(a, b);
        Adder adder2 = HalfAdder(adder1.s, c);
        char  carry  = BitOr(adder1.c, adder2.c);
        
        return new Adder(adder2.s, carry);
    }
    
    private static char BitAnd(char x, char y)
    {
        return AndTab[Index(x, y)];
    }
    
    private static char BitOr(char x, char y)
    {
        return OrTab[Index(x, y)];
    }
    
    private static char BitXor(char x, char y)
    {
        return XorTab[Index(x, y)];
    }
   
    private static int Index(char x, char y)
    {
        return (x - ZeroBit) + (y - ZeroBit);
    }
    
    private static char Digit(String x, int i)
    {
        return i >= 0 && i < x.length() ?  x.charAt(i) : ZeroBit;
    }
    
    private void TestAdd()
    {
        Eval("0", "0", "0");
        Eval("0", "1", "1");
        Eval("1", "0", "1");
        Eval("1", "1", "10");
        Eval("111", "10", "1001");
        Eval("1111", "110", "10101");
        Eval("11", "1", "100");
        Eval("1111", "1111", "11110");
        Eval("10000", "10000", "100000");
    }
    
    private void Eval(String x, String y, String r)
    {
        String z = Add(x, y);
        
        System.out.printf("X[%s] + Y[%s] = Z[%s]\n", x, y, z);
        
        if (z.equalsIgnoreCase(r) == false)
        {
            throw new RuntimeException(
                "Computed result NOT EQUAL to expected result"
                );
        }
    }
}

- Ray Patch April 13, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#---------------------------------------Binary sum
binary1 = "1010001101"
binary2 = "111101"
def get_binary_sum(binary1,binary2):
binary_sum = ''
max_len=max(len(binary1),len(binary2))
#To fill with padding left if not of the same lenght
binary1=binary1.zfill(max_len)
binary2=binary2.zfill(max_len)
carry=0
for x in range(max_len-1,-1,-1 ):
r=carry
r+=1 if binary1[x]=='1' else 0
r+=1 if binary2[x]=='1' else 0
binary_sum =('1' if r % 2 == 1 else '0' ) + binary_sum
#update the new carry
carry= 0 if (r<2) else 1
if carry!=0 :
binary_sum = '1' + binary_sum
#print(binary_sum)
return binary_sum
print(get_binary_sum(binary1,binary2))
#To check if the binary sum is correct we can make use of the bin function
sum = bin(int(binary1, 2) + int(binary2, 2))
# Printing result
print(sum[2:])

- Hermasoft September 02, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
#include <iostream>
#include <string>
#include <bitset>


using namespace std;

string add_two_strings(string s1, string s2){
int i = s1.length() - 1;
int j = s2.length() - 1;
string result;
int carry = 0;
for(; i >= 0 ;){
if(s1[i] == '1' && (s1[i--] == s2[j--])){
if(carry){
result += '1';
}
else{
result += '0';
carry = 1;
}
}else if(s1[i] == '0' && (s1[i--] == s2[j--])){
if(carry){
result += '1';
carry = 0;
}
else{
result += '0';
}
}else{
if(carry){
result += '0';
carry = 1;
}
else{
result += '1';
}
}
}

if(carry){
for(;j >= 0;){
if (s2[j--]){
result += '0';
}else{
result += '1';
carry = 0;
}
}
}else{
for(;j >= 0;){
result += s2[j--];
}
}

if(carry)
result += '1';

cout << "result " << result << " " << carry << endl;

for(int i = 0, j = result.size() - 1 ; i < result.size(), j >=0 ; i++, j--){
char t = result[i];
result[i] = result[j];
result[j] = t;
if(i >= j) break;
}
return result;
}
int main() {
string s1 = "1110011100001";
string s2 = "1111111110001";

string result="";

if(s1.length() <= s2.length()){
result = add_two_strings(s1,s2);
}else{
result = add_two_strings(s2,s1);
}

cout << s1 << " " << s2 << endl;
int s1_size = s1.size();
char * end;
long int s1_int = strtol (s1.c_str(),&end,2);
long int s2_int = strtol (s2.c_str(),&end,2);
long int res_int = strtol (result.c_str(),&end,2);

cout << s1_int << " " << s2_int << " " << s1_int + s2_int << " " << result << " " << res_int ;



return 0;
}

}}

- rsltgy October 03, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(max(s1,s2)), with test code.

{{

#include <iostream>
#include <string>
#include <bitset>


using namespace std;

string add_two_strings(string s1, string s2){
int i = s1.length() - 1;
int j = s2.length() - 1;
string result;
int carry = 0;
for(; i >= 0 ;){
if(s1[i] == '1' && (s1[i--] == s2[j--])){
if(carry){
result += '1';
}
else{
result += '0';
carry = 1;
}
}else if(s1[i] == '0' && (s1[i--] == s2[j--])){
if(carry){
result += '1';
carry = 0;
}
else{
result += '0';
}
}else{
if(carry){
result += '0';
carry = 1;
}
else{
result += '1';
}
}
}

if(carry){
for(;j >= 0;){
if (s2[j--]){
result += '0';
}else{
result += '1';
carry = 0;
}
}
}else{
for(;j >= 0;){
result += s2[j--];
}
}

if(carry)
result += '1';

cout << "result " << result << " " << carry << endl;

for(int i = 0, j = result.size() - 1 ; i < result.size(), j >=0 ; i++, j--){
char t = result[i];
result[i] = result[j];
result[j] = t;
if(i >= j) break;
}
return result;
}
int main() {
string s1 = "1110011100001";
string s2 = "1111111110001";

string result="";

if(s1.length() <= s2.length()){
result = add_two_strings(s1,s2);
}else{
result = add_two_strings(s2,s1);
}

cout << s1 << " " << s2 << endl;
int s1_size = s1.size();
char * end;
long int s1_int = strtol (s1.c_str(),&end,2);
long int s2_int = strtol (s2.c_str(),&end,2);
long int res_int = strtol (result.c_str(),&end,2);

cout << s1_int << " " << s2_int << " " << s1_int + s2_int << " " << result << " " << res_int ;



return 0;
}


}}

- rsltgy October 03, 2021 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More