## Facebook Interview Question for Software Engineer / Developers

Team: iOS
Country: United States
Interview Type: In-Person

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

``````public static String addBinary(String s1,String s2) {
if(s1 == null || s2 == null) {
return "";
}
int first = s1.length()-1;
int second = s2.length()-1;
StringBuilder sb = new StringBuilder();
int carry =0 ;
int curr = 0;
while(first >=0 || second >=0) {
int firstValue = (first < 0) ? 0 : s1.charAt(first)-'0';
int secondValue =  (second < 0)? 0: s2.charAt(second)-'0';
int sum = firstValue + secondValue + carry;

carry = sum >> 1;
sum = sum & 1;

sb.insert(0, (sum==0 ? '0' : '1'));
first--;
second--;
}
return sb.toString();
}``````

Comment hidden because of low score. Click to expand.
2

This is an elegantly concise approach! I still fill like you missed to tell the complexity of the approach. Apparently would be O(n) but I feel like it's actually O(n^2) because of the use of StringBuffer.insert(...) method. In the first iteration will shift 0 characters, in the second iteration will shift 1, and so on until the n-th iteration, when it will shift n-1 characters. In summary, all StringBuffer.insert(...) will have a complexity of O(0+1+...+(n-1)), equivalent to O(n * (n-1) / 2), equivalent to O(n^2).
Just a slight tweak using a primitive char array instead of a StringBuffer, filled from the bottom frontward would turn this elegant approach complexity to linear. Then, just return new String(myPrimitiveArrayOfChars);

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

You missed one case. After the loop, if the carry=1, we should append '1' to the front of the result.

Test case: "1100101", "11001011"
It should be "100110000"

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

If you insert sum into the first position, reallocation and copy will occur which makes your algorithm O(N^2)

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

``````//Add two strings of binary char
//String can be of diff length

void reverse(char arr[], int low, int high)
{

while(low < high)
{
arr[low] = arr[low]^arr[high];
arr[high] = arr[low]^arr[high];
arr[low] = arr[low]^arr[high];
low++;
high--;

}

}

{
int s1 = strlen(str1);
reverse(str1,0,s1-1);

int s2 = strlen(str2);
reverse(str2,0,s2-1);

int s = (s1 > s2 ? s1 : s2)+1;

char *p = new char[s];

int i = 0;
int j = 0;
int k = -1;

int carry = 0;

int bit1 = 0;
int bit2 = 0;

while(i < s1 && j < s2)
{

bit1 = str1[i++] - '0';
bit2 = str2[j++] - '0';
p[++k] = (bit1^bit2^carry) + '0';
carry = ((bit1&bit2)^carry)^((bit1^bit2)&carry);
}

while(i < s1)
{
bit1 = str1[i] - '0';
p[++k] = bit1^carry + '0';
carry = bit1*carry;
i++;
}

while(j < s2)
{
bit2 = str2[j] - '0';
p[++k] = bit2^carry;
carry = bit2*carry;
j++;
}

if(carry == 1)
{
p[++k] = '1';
}

reverse(p,0,k);

p[++k] = '\0';
return p;
}
int main()
{
char arr1[] = "10110101";
char arr2[] = "11001110";
cout<<sumPtr<<endl;

delete []sumPtr;//delete memory that allocated using new
return 0;
}``````

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

Code in c:

``````#include <stdio.h>
#include <conio.h>
#include <string.h>
static int k;
void reve(char *str,int j)
{
int i=0;
while(i<j)
{
char temp=str[i];
str[i++]=str[j];
str[j--]=temp;
}
}

{
if(a=='0'&&b=='1')
{
sum2[0]='1',sum2[1]='0';
}
else if(a=='1'&&b=='1')
{
sum2[0]='1',sum2[1]='1';
}
return sum2;
}

void add3(char a,char b,char c,char *sum)
{
if(a=='0'&&b=='0'&&c=='0')
{
sum[0]='0';
sum[1]='0';
}
else if((a=='1'&&b=='0'&&c=='0')||(a=='0'&&b=='1'&&c=='0')
||(a=='0'&&b=='0'&&c=='1'))
{
sum[0]='1';
sum[1]='0';
}
else if((a=='1'&&b=='1'&&c=='0')||(a=='0'&&b=='1'&&c=='1')
||(a=='1'&&b=='0'&&c=='1'))
{
sum[0]='0';
sum[1]='1';
}
else if(a=='1'&&b=='1'&&c=='1')
{
sum[0]='1';
sum[1]='1';
}
}

void traverse(char *str1,char *str2,char *s,char *str3,char c)
{
int i,j;
for(i=strlen(str2)-1,j=strlen(str1)-1;i>=0;i--,j--)
{
if(s[1]=='0')
str3[k++]=s[0];
else if(s[1]=='1')
{
str3[k++]=s[0];
c='1';
}
}
for(i=j;i>=0;i--)
{
if(c=='1')
{
if(s[1]=='0')
str3[k++]=s[0];
else
{
str3[k++]=s[0];
c='1';
}
}
else
{
str3[k++]=str1[i];
}
}

}
char *sum(char *str1,char *str2)
{
char str3[30],s[2],c='0';
int j,i;
if(strlen(str1)>strlen(str2))
{
traverse(str1,str2,s,str3,c);
}
else if(strlen(str1)<strlen(str2))
{
traverse(str2,str1,s,str3,c);
}
else
{
int i,j;
for(i=strlen(str2)-1,j=strlen(str1)-1;i>=0&&j>=0;i--,j--)
{
if(s[1]=='0')
str3[k++]=s[0];
else if(s[1]=='1')
{
str3[k++]=s[0];
c='1';
}
}
if(c=='1')
str3[k++]=c;
}
reve(str3,k-1);
for(i=0;i<k;i++)
printf("%c",str3[i]);
return str3;
}
int main()
{
char str1[]="1001";
char str2[]="100";
char *str3=sum(str1,str2);
}``````

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

Solution in Objective-C, leveraging the "category" feature of such language, that enables to aggregate methods to existing classes. In this case, the approach consists in aggregating a sumBinaryString:(NSString*) instance method to class NSString. The complexity is linear --i.e., O(n).

Tests first:

``````#import <XCTest/XCTest.h>
#import "NSString+Binary.h"

@interface CSPBinaryStringSumTests : XCTestCase

@end

@implementation CSPBinaryStringSumTests {
NSError* error_;
}

- (void)setUp
{
[super setUp];
error_ = nil;
}

- (void)tearDown
{
error_ = nil;
[super tearDown];
}

- (void)testNormalCase
{
NSString *op1 = @"101", *op2 = @"11";
XCTAssertEqualObjects(@"1000", [op1 sumBinaryString:op2]);
}

- (void)testNullCase
{
XCTAssertNil([@"1" sumBinaryString:nil]);
}

- (void)testUnusualYetValidInput
{
NSString *op1 = @"0000000000000101", *op2 = @"0000000000000000000000000011";
XCTAssertEqualObjects(@"1000", [op1 sumBinaryString:op2]);
}

- (void)testZeroes
{
NSString *op1 = @"0000000000000", *op2 = @"0000000000000000000000000011";
XCTAssertEqualObjects(@"11", [op1 sumBinaryString:op2]);

op1 = @"0000000000000101", op2 = @"00000000000000000000000000";
XCTAssertEqualObjects(@"101", [op1 sumBinaryString:op2]);

op1 = @"0000000000000", op2 = @"00000000000000000000000000";
XCTAssertEqualObjects(@"0", [op1 sumBinaryString:op2]);
}

- (void)testInvalidBinaries
{
NSString *op1 = @"I'm not a binary string";
XCTAssertNil([op1 sumBinaryString:@"101" error:&error_]);

XCTAssertNil([@"101" sumBinaryString:@"I'm not either" error:&error_]);
}

- (void)testHugeInput
{
NSString *op1 = @"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101",
*op2 = @"101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101011",
*expected = @"10000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000";

XCTAssertEqualObjects(expected, [op1 sumBinaryString:op2 error:&error_]);
}

@end``````

``````#import <Foundation/Foundation.h>

extern NSString * const NSStringBinaryErrorDomain;

@interface NSString (Binary)

/**
* Sums the operand to the self string, assuming both contain only binary chars.
* @param operand the binary number, represented as a string of '1's and '0's.
* @return a new string containing the binary repressentation of the sum of the
* input. Nil in case some error happens with the input.
*/
- (NSString*)sumBinaryString:(NSString*)operand;

/**
* Sums the operand to the self string, assuming both contain only binary chars.
* @param operand the binary number, represented as a string of '1's and '0's.
* @param error a reference to an NSError* where the reasons for failure will be
* left, if a failure happened at all.
* @return a new string containing the binary repressentation of the sum of the
* input. Nil in case some error happens with the input (check error in such
* case).
*/
- (NSString*)sumBinaryString:(NSString*)operand error:(NSError* __strong *) error;

@end``````

Category implementation:

``````#import "NSString+Binary.h"

NSString * const NSStringBinaryErrorDomain = @"NSStringBinaryDomain";

// Convenience function that assigns the longest string to the output parameter
// longest, the shortest to shortest.
// Returns the length of the longest.
NSUInteger assignLongestAndShortest(NSString **longest, NSString **shortest,
NSString *str1, NSString *str2)
{
if ([str1 length] > [str2 length]) {
*longest = str1; *shortest = str2;
} else {
*longest = str2; *shortest = str1;
}

return [*longest length];
}

@implementation NSString (Binary)

- (NSString*)sumBinaryString:(NSString*)operand
{
return [self sumBinaryString:operand error:nil];
}

- (NSString*)sumBinaryString:(NSString*)operand error:(NSError* __strong *)error
{
NSString *result = nil;
NSInteger statusCode = 0;
id statusObject;

if (operand) {
NSString *longest, *shortest;
// we'll work on a temporaty C-array whose length is the length of the
// longest input string plus 1 for a potential carry.
NSUInteger bufferLength = assignLongestAndShortest(&longest, &shortest,
self, operand) + 1;
unichar *buffer = new unichar[bufferLength]();

@try {
NSUInteger index;
BOOL carry;

// this algorithm iterates with O(n) where n is the length of the
// longest string. It iterates backward over the strings, in two
// phases.
// The first phase is while both strings have common positions
// covered, starting from the end.
for (index = 1, carry = NO; index <= [shortest length]; ++index) {
// Both characters are compared to calculate the resulting some
// at that position, taking into account a potential carry from
// the previous iteration.
switch ([longest characterAtIndex:([longest length] - index)]) {
case '0':
switch ([shortest characterAtIndex:([shortest length] - index)]) {
case '0':
buffer[bufferLength - index] = carry ? '1' : '0';
carry = NO;
break;

case '1':
buffer[bufferLength - index] = carry ? '0' : '1';
break; // in this scenario, carry wouldn't change

default:
// If the shortest string has other than 1 or 0,
// the string is a malformed binary.
statusCode = 200;
statusObject = shortest;
break;
}
break;

case '1':
switch ([shortest characterAtIndex:([shortest length] - index)]) {
case '0':
buffer[bufferLength - index] = carry ? '0' : '1';
break;

case '1':
buffer[bufferLength - index] = carry ? '1' : '0';
carry = YES;
break;

default:
statusCode = 200;
statusObject = shortest;
break;
}
break;

default:
// the longest is a malformed binary string
statusCode = 200;
statusObject = longest;
break;
}
// short-circuit if statusCode isn't 0 anymore.
if (statusCode) break;
}

if (!(statusCode)) {
// Second phase of the loop over longest: this portion only covers
// the most-significant section of the longest that doesn't have
// counterpart in the shortest.
for (; index <= [longest length]; ++index) {
switch ([longest characterAtIndex:([longest length] - index)]) {
case '0':
buffer[bufferLength - index] = carry ? '1' : '0';
carry = NO;
break;

case '1':
buffer[bufferLength - index] = carry ? '0' : '1';
carry = YES;
break;

default:
statusCode = 200;
statusObject = longest;
break;
}
if (statusCode) break;
}

if (!(statusCode)) {
// last check after finishing with the longest: is there any
// carry left? If so, turn on the first char.
buffer[0] = carry ? '1' : '0';
carry = NO;

// Now, let's skip all '0' until finding the canonical most
// significant '1'.
for (index = 0;
(buffer[index]) == '0' && (index < bufferLength - 1);
++index);

result =
[NSString stringWithCharacters:buffer+index
length:bufferLength - index];
}
}
}
@finally {
delete[] buffer;
}
} else {
// The operand is nil, sum skipped.
statusCode = 100;
}

if ((statusCode) && (error)) {
[self p_populateError:error forCode:statusCode andObject:statusObject];
}

return result;
}

// Produces an NSError in the NSStringBinaryErrorDomain domain based on the
// status code received as parameter.
- (void) p_populateError:(NSError* __strong *)error
forCode:(NSInteger)code
andObject:(id)object
{
if (error) {
NSMutableDictionary *userInfo = [NSMutableDictionary dictionary];

switch (code) {
case 100:
[userInfo setObject:@"Binary sum skipped."
forKey:NSLocalizedDescriptionKey];
[userInfo setObject:@"Operand is nil"
forKey:NSLocalizedFailureReasonErrorKey];
[userInfo setObject:@"Provide a binary operand"
forKey:NSLocalizedRecoverySuggestionErrorKey];
break;

case 200:
[userInfo setObject:@"Binary sum aborted."
forKey:NSLocalizedDescriptionKey];
[userInfo setObject:[NSString stringWithFormat:
@"Operand isn't binary: \"%@\"", object]
forKey:NSLocalizedFailureReasonErrorKey];
[userInfo setObject:@"Provide a binary operand"
forKey:NSLocalizedRecoverySuggestionErrorKey];
break;

default:
[userInfo setObject:@"Undetermined error"
forKey:NSLocalizedDescriptionKey];
}

*error = [NSError errorWithDomain:NSStringBinaryErrorDomain
code:code userInfo:userInfo];
}
}

@end``````

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

this solutions is a complete non sense.

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

A simple O(n) solution:
=================================================

``````package strings;

public void addBinaryStrings(String a, String b){

int ea = a.length() - 1;
int eb = b.length() - 1;

// Resulting string will be of length more than one or equal to max string
int i = Math.max(ea, eb) + 1;
char[] finalStr = new char[i + 1];

int carry = 0;

while( i > 0){

int curVal = 0;

if(ea >= 0)
curVal += a.charAt(ea) - '0';

if(eb >= 0)
curVal += b.charAt(eb) - '0';

curVal += carry;

// Make sure all the possible sums - 0,1,2,3 are taken care of
if(curVal == 1){

finalStr[i] = '1';
}
else if(curVal == 2){
finalStr[i] = '0';
carry = 1;
}
else if(curVal == 3){
finalStr[i] = '1';
carry = 1;
}
else{
finalStr[i] = '0';
}

i--;
ea--;
eb--;
}

// Make sure carry from the last operation is taken care of
if(carry == 1)
finalStr[0] = '1';
else
finalStr[0] = '0';

System.out.println(String.valueOf(finalStr));
}

public static void main(String[] args){

}

}``````

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

I believe you're missing to turn carry off (carry = 0) right after consuming it:

``````curVal += carry;
carry = 0; // <-- this line added by me``````

Otherwise, correct me if I'm wrong, once you carry for the first time, you'll keep adding 1 to curVal for all the remaining iterations.

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

If you turn off the carry value, in the next iteration the carry won't be added to the current sum. So no, you should let it be as is.
Plus the carry value is updated in the case the sum is 2 & 3, which affects the next iteration. I find this solution to be pretty good.

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

``````int oneInt = Integer.parseInt(oneString, 2);
int twoInt = Integer.parseInt(twoString, 2);

int sum = oneInt + twoInt;
return Integer.toBinaryString(sum);``````

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

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

public static String sum(String s1,String s2){
if(s1.length()==0||s2.length()==0) return s1.length()==0 ? s1 : s2;
else{
int carry=0;int sum=0;
StringBuffer sb=new StringBuffer();
int first=s1.length()-1;int second=s2.length()-1;
while(first>=0||second>=0){
int firstValue=first<0? 0 : Integer.valueOf(s1.charAt(first));
int secondValue=second<0? 0 : Integer.valueOf(s2.charAt(second));
sum=firstValue+secondValue+carry;
carry=sum>>1;
sum&=1;
sb.append(sum==0? "0":"1");
first--;second--;
}
return sb.toString();
}

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

My impression is that this solution, like others posted here, produces an output whose most significant character is at the end of the string.
For example, summing "11" and "1" should produce "100". But this approach will produce "001" if I'm not misunderstanding something.

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

``````public class BinaryConverter {
public static void main(String[] args) {
String str1 = "1010101010";
String str2 = "0110";
int number1 = getIntegerFromBinary(str1);
int number2 = getIntegerFromBinary(str2);
System.out.println("The sum is :: "+ (number1+number2));
}

private static int getIntegerFromBinary(String str) {
char[] arr = str.toCharArray();
int sum = 0;
for(int i = arr.length-1,j=0;i>=0;i--,j++){
if(arr[i] == '1')
sum = (int) (sum + Math.pow(2, j));
}
return sum;
}
}``````

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

The complexity is O(n).

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

public static String Add(String s1, String s2)
{
StringBuilder result = new StringBuilder();

if(s1 == null && s2 == null)
{
result = null;
}
else if(s1 == null && s2 != null)
{
result.append(s2);
}
else if(s1 != null && s2 == null)
{
result.append(s1);
}
else
{
int carry = 0;

int s1EndIndex = s1.length() - 1;
int s2EndIndex = s2.length() - 1;

while(s1EndIndex >= 0 || s2EndIndex >= 0)
{
int s1Char = ( s1EndIndex < 0) ? 0 : s1.charAt(s1EndIndex) - '0';
int s2Char = ( s2EndIndex < 0) ? 0 : s2.charAt(s2EndIndex) - '0';

int sum = s1Char + s2Char + carry;

if(sum == 0)
{
result.insert(0, '0');
}
else if(sum == 1)
{
result.insert(0, '1');
}
else if(sum == 2)
{
result.insert(0, '0');
carry = 1;
}
else
{
result.insert(0, '1');
carry = 1;
}

s1EndIndex--;
s2EndIndex--;
}

if(carry == 1)
{
result.insert(0, '1');
}

}

return result.toString();

}

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

PHP:

``````function getSumOfBinaryNumbers(\$num1, \$num2)
{
\$num1Digits = str_split(\$num1);
\$num1Size = count(\$num1Digits);
\$num2Digits = str_split(\$num2);
\$num2Size = count(\$num2Digits);
\$count = abs(\$num1Size - \$num2Size);
if (\$num1Size > \$num2Size) {
for (\$i = 0; \$i < \$count; \$i++) {
array_unshift(\$num2Digits, '0');
}
} else if (\$num1Size < \$num2Size) {
for (\$i = 0; \$i < \$count; \$i++) {
array_unshift(\$num1Digits, '0');
}
}
\$resultDigits = array();
\$higherBitShift = false;
\$shiftedBit = \$resultDigit = 0;
\$size = count(\$num1Digits) - 1;
for (\$i = \$size; \$i >= 0; \$i--) {
// 1 + 1
if (\$num1Digits[\$i] == 1 && \$num2Digits[\$i] == 1) {
\$resultDigit = 0 + \$shiftedBit;
\$higherBitShift = true;
\$shiftedBit = 1;
}
// 1 + 0 or 0 + 1 or 0 + 0
else {
\$resultDigit = (int) \$num1Digits[\$i] + (int) \$num2Digits[\$i];
if (\$resultDigit == 1 && \$higherBitShift) {
\$resultDigit = 0;
\$shiftedBit = 1;
\$higherBitShift = true;
} else {
\$resultDigit += \$shiftedBit;
\$higherBitShift = false;
\$shiftedBit = 0;
}
}
\$resultDigits[\$i] = \$resultDigit;
if (\$higherBitShift && \$i == 0) {
array_push(\$resultDigits, 1);
}
}

return ltrim(implode('', array_reverse(\$resultDigits)), '0');
}``````

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

void BinaryAddition(string& str1,string& str2, string& strFinal)
{
int nCarry=0;
int nFirstLength=str1.length();
int nSecondLength=str2.length();
int nFirstNumber=0;
int nSecondNumber=0;
int nSum=0;
while((nFirstLength>0) && (nSecondLength>0))
{
nFirstNumber=str1.at(nFirstLength-1)-'0';
nSecondNumber=str2.at(nSecondLength-1)-'0';
nSum=nFirstNumber+nSecondNumber+nCarry;
nCarry=nSum>>1;
nSum=nSum & 1;
(nSum>0)?strFinal.insert(0,"1"):strFinal.insert(0,"0");
nFirstLength--;
nSecondLength--;
}
while(nFirstLength>0)
{
nFirstNumber=str1.at(nFirstLength-1)-'0';
nSum=nFirstNumber+nCarry;
nCarry=nSum>>1;
nSum=nSum & 1;
(nSum>0)?strFinal.insert(0,"1"):strFinal.insert(0,"0");
nFirstLength--;
}
while(nSecondLength>0)
{
nSecondNumber=str2.at(nSecondLength-1)-'0';
nSum=nSecondNumber+nCarry;
nCarry=nSum>>1;
nSum=nSum & 1;
(nSum>0)?strFinal.insert(0,"1"):strFinal.insert(0,"0");
nFirstLength--;
}
if(nCarry!=0)
strFinal.insert(0,"1");
}

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

N=length of one string, M=length of the other string. O(max(N,M)) time complexity and O(max(N,M) space complexity algorithm. I didn't insert sum into the first position of the result string because it may cause reallocation and copying and in result, complexity may become O(max(N,M)^2). Instead, I append the sum and return the reversed string.

``````auto add2 = [](const string& ons1, const string& ons2) {
string ret;
int carry = 0;
auto ns1 = ons1.c_str(), ns2 = ons2.c_str();
int i = ons1.length()-1, j = ons2.length()-1;
if (ons1.length() < ons2.length()) {
swap(ns1, ns2);
swap(i,j);
}
ret.reserve(i+2); // pre-allocate space for longer string length + possible last carry to avoid reallocation
int n1 = 0, n2 = 0;
for (; i >= 0; --i, --j) {
n1 = ns1[i] - '0';
n2 = j >= 0 ? ns2[j] - '0' : 0;
ret.push_back((n1 ^ n2 ^ carry) + '0');
carry = (n1 & n2) | (n1 & carry) | (n2 & carry);
}
if (carry) {
ret.push_back(carry + '0');
}
reverse(ret.begin(), ret.end());
return ret;
};``````

Two more words:
1. Made ns1 the longer string to avoid additional O(max(N,M)) comparisons for i >= 0 when calculating n1 and comparisons for j >= 0 loop exit condition.
2. Computed sum and carry using only bit operations which is faster than arithmetic operations.

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

This problem is kinda simple and here is my Java code to solve this problem -:

``````public class BinaryStringAdder {

public static ArrayList<Integer> binaryAdder(ArrayList<Integer> num1, ArrayList<Integer> num2){
Collections.reverse(num1);
Collections.reverse(num2);
int carry = 0;
ArrayList<Integer> sum = new ArrayList<Integer>();
for(int i = 0; i < num2.size(); ++i){
int temp = num1.get(i) + num2.get(i) + carry;
carry = temp/2;
}
for(int i = num2.size(); i < num1.size(); ++i){
int temp = num1.get(i) + carry;
carry = temp/2;
}

if(carry != 0)

Collections.reverse(sum);

return sum;
}

public static void main(String[] args) throws IOException{
ArrayList<Integer> sum;
if(biNum1.size() >= biNum2.size())
else

for(int i = 0; i < sum.size(); ++i)
System.out.print(sum.get(i));
}
}``````

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

``````string addBinaryStrings(string a, string b)
{
string c;
int carry = 0;
int lena = a.length(), lenb = b.length();
int i=lena-1, j=lenb-1, k=max(lena, lenb)-1;

c.resize(k+1, '0');

while (i>=0 && j>=0) {
c[k] = ((a[i]-'0') ^ (b[j]-'0') ^ carry) + '0';
carry = (carry + (a[i]-'0') + (b[j]-'0')) > 1 ? 1 : 0;
i--,j--,k--;
}

while (i>=0) {
c[k] = (carry ^ (a[i]-'0')) + '0';
carry = (carry+(a[i]-'0')) > 1 ? 1 : 0;
i--,k--;
}

while (j>=0) {
c[k] = (carry ^ (b[j]-'0')) + '0';
carry = (carry+(b[j]-'0')) > 1 ? 1 : 0;
j--,k--;
}

if (carry) return "1" + c;

return c;
}``````

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

Code in java. Complexity is O(N)

public String addBinary(String n1, String n2){
int carry = 0;
int l = Math.min(n1.length(), n2.length());

for(int i=1; i <= l ; i++){
int digit = (n1.charAt(n1.length()-i) - '0') ^ (n2.charAt(n2.length()-i)- '0') ^ carry;
carry = (carry ==0)?(n1.charAt(n1.length()-i) - '0') & (n2.charAt(n2.length()-i)- '0'):
((n1.charAt(n1.length()-i) - '0') | (n2.charAt(n2.length()-i)- '0')) & carry;
}

if(n1.length() > n2.length()){

for(int i= l+1; i <n1.length() ; i++){
int digit = (n1.charAt(n1.length()-i) - '0') ^ carry;
carry = carry & (n1.charAt(n1.length()-i) - '0');
}
}
else if(n1.length() < n2.length()){

for(int i= l+1; i <=n2.length() ; i++){
int digit = (n2.charAt(n2.length()-i) - '0') ^ carry;
carry = carry & (n2.charAt(n2.length()-i) - '0');
}
}

}

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

Code in Java, complexity is O(N)

``````public String addBinary(String n1, String n2){
int carry = 0;
int l = Math.min(n1.length(), n2.length());

for(int i=1; i <= l ; i++){
int digit = (n1.charAt(n1.length()-i) - '0') ^ (n2.charAt(n2.length()-i)- '0') ^ carry;
carry = (carry ==0)?(n1.charAt(n1.length()-i) - '0') & (n2.charAt(n2.length()-i)- '0'):
((n1.charAt(n1.length()-i) - '0') | (n2.charAt(n2.length()-i)- '0')) & carry;
}

if(n1.length() > n2.length()){

for(int i= l+1; i <n1.length() ; i++){
int digit = (n1.charAt(n1.length()-i) - '0') ^ carry;
carry = carry & (n1.charAt(n1.length()-i) - '0');
}
}
else if(n1.length() < n2.length()){

for(int i= l+1; i <=n2.length() ; i++){
int digit = (n2.charAt(n2.length()-i) - '0') ^ carry;
carry = carry & (n2.charAt(n2.length()-i) - '0');
}
}

}``````

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

``````public long sum(String x, String y)
{
if(x == null || y == null)
throw new IllegalArgumentException("X or/and y is null");
if(x.length > 64 || y.length > 64)
throw new IllegalArgumentException("xlen, ylen exceeds 64");

long xl = parseAsLong(x);
long yl = parseAsLong(y);
return xl + yl;
}

private long parseAsLong(String s)
{
long l = 0L;
for(int i = 0; i < s.length; i++) {
Char c = s.getAt(i);
if(c == '0')
continue;
else if(c == '1')
l |= (1L << i);
else
throw new IllegalArgumentException("Invalid character at index" + i);
}
return l;
}``````

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

``````public long sum(String x, String y)
{
if(x == null || y == null)
throw new IllegalArgumentException("X or/and y is null");
if(x.length > 64 || y.length > 64)
throw new IllegalArgumentException("xlen, ylen exceeds 64");

long xl = parseAsLong(x);
long yl = parseAsLong(y);
return xl + yl;
}

private long parseAsLong(String s)
{
long l = 0L;
for(int i = 0; i < s.length; i++) {
Char c = s.getAt(i);
if(c == '0')
continue;
else if(c == '1')
l |= (1L << i);
else
throw new IllegalArgumentException("Invalid character at index" + i);
}
return l;
}``````

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

``````public long sum(String x, String y)
{
if(x == null || y == null)
throw new IllegalArgumentException("X or/and y is null");
if(x.length > 64 || y.length > 64)
throw new IllegalArgumentException("xlen, ylen exceeds 64");

long xl = parseAsLong(x);
long yl = parseAsLong(y);
return xl + yl;
}

private long parseAsLong(String s)
{
long l = 0L;
for(int i = 0; i < s.length; i++) {
Char c = s.getAt(i);
if(c == '0')
continue;
else if(c == '1')
l |= (1L << i);
else
throw new IllegalArgumentException("Invalid character at index" + i);
}
return l;
}``````

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

``````public static long sum(String x, String y)
{
if(x == null || y == null)
throw new IllegalArgumentException("X or/and y is null");
if(x.length() > 64 || y.length() > 64)
throw new IllegalArgumentException("xlen, ylen exceeds 64");

long xl = parseAsLong(x);
System.out.println(xl);
long yl = parseAsLong(y);
System.out.println(yl);

return xl + yl;
}

private static long parseAsLong(String s)
{
long l = 0L;
int n = s.length();
for(int i = 0; i < n; i++) {
char c = s.charAt(i);
if(c == '0')
continue;
else if(c == '1')
l |= (1L << (n - i - 1));
else
throw new IllegalArgumentException("Invalid character at index" + i);
}
return l;
}``````

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

``````public static String add(String str1, String str2) {

int i = str1.length() - 1;
int j = str2.length() - 1;
boolean rem = false;
StringBuilder builder = new StringBuilder();

while (i >= 0 && j >= 0) {

char a = str1.charAt(i--);
char b = str2.charAt(j--);

if (a == '1' && b == '1') {

if (rem) {
builder.append('1');
} else {
builder.append('0');
}
rem = true;

} else if (a == '0' && b == '0') {
if (rem) {
builder.append('1');
} else {
builder.append('0');
}
rem = false;

} else {

if (rem) {
builder.append('0');
} else {
builder.append('1');
}
}
}

int c = i > j ? i : j;
String strRem = i > j ? str1 : str2;

while (c >= 0) {
char a = strRem.charAt(c--);
if (a == '0' && rem) {
builder.append('1');
rem = false;
} else if (a == '1' && rem) {
builder.append('0');
} else {
builder.append(a);
}
}
if (rem)
builder.append('1');
return builder.reverse().toString();
}``````

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

``````public void addBinaries(String inputString1, String inputString2){
int len1 = inputString1.length();
int len2 = inputString2.length();
StringBuffer sb1 = new StringBuffer(inputString1).reverse();
StringBuffer sb2 = new StringBuffer(inputString2).reverse();
StringBuffer sb3 = new StringBuffer();

if(len1 > len2){
}else{
}
int carry = 0;

for (int i = 0; i < sb1.length(); i++) {
int sum = carry + Integer.valueOf(String.valueOf(sb1.charAt(i))) + Integer.valueOf(String.valueOf(sb2.charAt(i)));
if(sum == 0){
sb3.append(sum);
}else if(sum > 0 && sum % 2 == 0){
sb3.append(0);
carry = 1;
}else if(sum == 1){
sb3.append(1);
}else if(sum > 0 && sum > 2){
sb3.append(1);
carry = 1;
}
}

if(carry == 1){
sb3.append(1);
}

System.out.println(sb3.reverse());
}

private void padZero(StringBuffer sb, int len) {
while(sb.length()!=len){
sb.append(0);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

before return statement :
if (carry > 0 ) {
sb.insert(0,'1');
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
#include<string.h>
int main()
{
char s1[]="01011111";
char s2[]="11000";
char s3[20],carry='0';
int c1=0,c2=0,i,j,k=0;
c1=sizeof(s1)/sizeof(s1[0]);
c2=sizeof(s2)/sizeof(s2[0]);
i=c1;
j=c2;
while(i>=0&&j>=0)
{
if(s1[i]==s2[j])
{
if(s1[i]=='1')
{
if(carry=='0')
{
s3[k]='0';
}
else
s3[k]='1';
carry='1';
}
else
{
if(carry=='0')
s3[k]='0';
else
{
s3[k]='1';
}
carry='0';
}
}
else
{
if(carry=='0')
{
s3[k]='1';
carry='0';
}
else
{
s3[k]='0';
carry='1';
}
}
k++;
j--;
i--;
}

if(i>=0)
{
while(i>=0)
{
if(s1[i]=='0')
{
if(carry=='1')
s3[k]='1';
else
s3[k]='0';
carry='0';
}
else
{
if(carry=='1')
{
s3[k]='0';
carry='1';
}
else
{
s3[k]='1';
carry='0';
}
}
i--;
k++;
}
}
else
{
while(j>=0)
{
if(s2[j]=='0')
{
if(carry=='1')
s3[k]='1';
else
s3[k]='0';
}
else
{
if(carry=='1')
{
s3[k]='0';
carry='1';
}
else
s3[k]='1';
}
j--;
k++;
}
}
k--;

while(k>1)
{
printf("%c",s3[k]);
k--;
}

return 0;
}
Time complexity:O(n)
where 'n' is length of bigger string

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.