Facebook Interview Question Android Engineers
Country: UK, London
Interview Type: Phone Interview
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?
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
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') )
/**
* @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);
}
}
/*
* @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;
}
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);
}
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());
}
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());
}
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();
}
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();
}
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;
}
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
/* 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
}
}
/* 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
}
}
# 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)))
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)))
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);
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;
}
#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;
}
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;
}
#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;
}
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();
}
}
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();
}
}
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)
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'))
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'
};
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;
}
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;
}
#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;
}
#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;
}
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;
}
#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;
}
#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;
}
#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;
}
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}`);
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");
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");
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;
}
// 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"
}
}
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)
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")
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"
);
}
}
}
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"
);
}
}
}
#---------------------------------------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:])
{{
#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;
}
}}
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;
}
}}
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)
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')
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]
{{
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)
}}
# 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)
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
- Simone Spaccarotella January 20, 2021// 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}`);