## Facebook Interview Question for Android Engineers

Country: UK, London
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 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}`);``````

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

My naive implementation. (Kotlin)

/* Handling edge cases */
return ""

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

} else {
if(carryOn)
result.insert(0, '0')
else
result.insert(0, '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?

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

Improved solution

/* Handling edge cases */
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

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
}

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);
}
}``````

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;
}

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) {
} else {
}

plus = 1;

} else if (firstSub.equals(secondSub) && firstSub.equals("0")) {

if (plus == 1) {
} else {
}

plus = 0;

} else {

if (plus == 1) {
plus = 1;
} else {
plus = 0;
}
}

}

if (plus == 1) {
}

StringBuilder result = new StringBuilder();

for (int i = (res.size() - 1); i >= 0; i--) {
result.append(res.get(i));
}

System.out.print(" = " + result);
}``````

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());
}``````

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());
}``````

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();
}``````

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();
}``````

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;
}``````

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

``````def binary_add(s1, s2):
if len(s1) != len(s2):
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``````

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;

}

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

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
}
}``````

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;

}

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

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
}
}``````

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)))

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)))``````

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);``````

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()) {
}
for (char c : b.toCharArray()) {
}

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;
}``````

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;
}``````

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;
}

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;
}``````

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) {
(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;
}

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

class Solution {
public static void main(String[] args) {
}

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();
}
}

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

``````class Solution {
public static void main(String[] args) {
}

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();
}
}``````

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)``````

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

``````from itertools import zip_longest

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)

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'
};``````

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;
}``````

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;
}``````

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()
{
return 0;
}

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()
{
return 0;
}

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()
{
return 0;
}``````

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()
{
return 0;
}``````

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()
{
return 0;
}``````

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()
{
return 0;
}``````

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}`);``````

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");``````

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");``````

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'

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;

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;
}

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 {
}

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 {
}

if len(second) == 0 {
}

lastFirstIndex := len(first)-1
lastSecondIndex := len(second)-1

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"
}
}``````

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)``````

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)

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 };

{
{
this.s = s;
this.c = c;
}

public final char s;
public final char c;
}

public static void Test()
{
BinaryCircuit circuit = new BinaryCircuit();

}

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--);

i--;
}

if (carry == OneBit)
{
sum[0] = carry;
}

return new String(sum).trim();
}

char a,
char b
)
{
return new Adder(BitXor(a, b), BitAnd(a, b));
}

char a,
char b,
char c
)
{

}

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;
}

{
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)
{

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"
);
}
}
}``````

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 };

{
{
this.s = s;
this.c = c;
}

public final char s;
public final char c;
}

public static void Test()
{
BinaryCircuit circuit = new BinaryCircuit();

}

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--);

i--;
}

if (carry == OneBit)
{
sum[0] = carry;
}

return new String(sum).trim();
}

char a,
char b
)
{
return new Adder(BitXor(a, b), BitAnd(a, b));
}

char a,
char b,
char c
)
{

}

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;
}

{
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)
{

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"
);
}
}
}``````

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:])

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

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

using namespace std;

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()){
}else{
}

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;
}

}}

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;

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()){
}else{
}

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;
}

}}

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

``````s1 = "101101"
s2 = "111101"
expected_result = "1101010"

l1 = len(s1)
l2 = len(s2)
max_len = max(l1, l2)

s1 = s1[::-1]
s2 = s2[::-1]

sums = {
"000": ("0", "0"),
"100": ("1", "0"),
"010": ("1", "0"),
"001": ("1", "0"),
"110": ("0", "1"),
"101": ("0", "1"),
"011": ("0", "1"),
"111": ("1", "1"),
}

def binsum(e1, e2, rest):
return sums[e1 + e2 + rest]

result_digits = []

rest = "0"
for i in range(max_len):
e1 = s1[i] if i < l1 else "0"
e2 = s2[i] if i < l2 else "0"
binres, rest = binsum(e1, e2, rest)
result_digits.append(binres)

result_digits.append(rest)

result_value = "".join(result_digits)
result_value = result_value[::-1]

print(result_value)
print(result_value == expected_result)``````

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

``````def sumStrings(a,b):

lena = len(a)
lenb = len(b)

if lena > lenb:
diff = lena-lenb
b = '0'*diff+b
elif lena<lenb:
diff = lenb-lena
a = '0'*diff+a

final_string = ''
rest = '0'

for i in range(lena-1,-1,-1):

num_a = a[i]
num_b = b[i]

if num_a+num_b+rest=='111':
final_string = '1'+final_string
rest = '1'

elif num_a+num_b+rest=='011' or num_a+num_b+rest=='101' or num_a+num_b+rest=='110':
final_string = '0'+final_string
rest = '1'

elif num_a+num_b+rest=='000':
final_string = '0'+final_string
rest = '0'

elif num_a+num_b+rest=='001' or num_a+num_b+rest=='010' or num_a+num_b+rest=='100':
final_string = '1'+final_string
rest = '0'

final_string = rest+final_string

print(final_string)

sumStrings('101101','111101')``````

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

``````def sumstrings(a, b):
maxLen = max(len(a), len(b))
carry = '0'
totalStr = ''
for i in range(maxLen):
i = maxLen - i
if i >= len(a):
firstChar = '0'
secondChar = b[i]
elif i>= len(b)
firstChar = a[i]
secondChar = '0'
else:
firstChar= a[i]
secondChar = b[i]
if firstChar == secondChar:
total += carry
carry = firstChar
else:
total += ' 1'
carry = '0'
totalStr = totalStr[::-1]``````

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

{{
a = "111"
b = "111"

a = list(a)
b = list(b)
size_mx = max(len(a),len(b))
size_mn = min(len(a),len(b))

current_val = '0'
next_val = '0'
before_val = '0'
final_val = ''

for i in range(size_mx-1,-1, -1):
j = i - (size_mx-size_mn)

if (len(a)<len(b)):
a,b = b,a

if(i>=0):
val_a = a[i]
else:
val_a = '0'

if(j>=0):
val_b = b[j]
else:
val_b = '0'

print(val_a, val_b, i, j)

if(val_a != val_b):
if(before_val == '0'):
current_val = '1'
next_val = '0'
else:
current_val = '0'
next_val = '1'

if(val_a == val_b == '1'):
if(before_val == '0'):
current_val = '0'
next_val = '1'
else:
current_val = '1'
next_val = '1'

if(val_a == val_b == '0'):
if(before_val == '0'):
current_val = '0'
next_val = '0'
else:
current_val = '1'
next_val = '0'

final_val = current_val+final_val
before_val = next_val

if(before_val == '1'):
final_val = before_val+final_val

print(final_val)
}}

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

``````# input
a = '10101010'
b = '00100011'
res = ''
carry  = '0'

for i in range (len(a)) :
tmp_a = a[-i-1]
tmp_b = b[-i-1]
if ((tmp_a == '1' and  tmp_b == '0') or (tmp_a == '0' and  tmp_b == '1')) and carry  == '0' :
res  = '1' + res
elif ((tmp_a == '1' and  tmp_b == '0') or (tmp_a == '0' and  tmp_b == '1')) and carry  == '1' :
res  = '0' + res
elif ((tmp_a == '0' and  tmp_b == '0') ) and carry  == '1' :
res  = '1' + res
carry  = '0'
elif ((tmp_a == '0' and  tmp_b == '0') ) and carry  == '0' :
res  = '0' + res
elif ((tmp_a == '1' and  tmp_b == '1') ) and carry  == '1' :
res  = '1' + res
elif ((tmp_a == '1' and  tmp_b == '1') ) and carry  == '0' :
res  = '0' + res
carry  = '1'
else :
# check if you are missing anything
print(tmp_a + tmp_b)
print(res)``````

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

``````string addBinary(string a, string b) {
string ans{};
int carry = 0;
int i = a.length() - 1;
int j = b.length() - 1;

while (i >= 0 || j >= 0 || carry) {
if (i >= 0) {
carry += a[i--] - '0';
}

if (j >= 0) {
carry += b[j--] - '0';
}

ans += carry % 2 + '0';
carry /= 2;
}

reverse(ans.begin(), ans.end());
return ans;
}``````

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.

### 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.