BINADD - Editorial

striker22 · December 20, 2019, 4:34pm

The logic which I used was:

First make both the binary strings A and B of equal length if they are not of equal length.
As we know the length of the largest carry sequence will be the answer, I just need to find the maximum carry sequence length I have occurred till now.
I will iterate from left to right i.e. LSB to MSB, and if:
if carry + A[i] + B[i] == 2 means that bit marks the start of carry sequence, so ++counter and carry = 1.
If carry + A[i] + B[i] == 3 means that bit will generate the carry but the length of sequence will reset to 1 i.e. counter = 1 and carry = 1.
If carry + A[i] + B[i] == 1 or 0 means that bit will mark the end of the sequence, but the carry generated will be resolved here, so the length of the sequence will reset to 0. i.e. counter = 0 and carry = 0.

if(counter > max_counter) {
     max_counter = counter;
}

Answer would be max_counter + 1.
You can refer to the solution here:
Solution Link: CodeChef: Practical coding for everyone

Important Test-Cases

Input

Output Data

You can also refer to the link: Competitive-Programming/Code-Chef/Addition at master · strikersps/Competitive-Programming · GitHub for more test-cases and the solution.

You can refer to this paper which gives an average case analysis of the algorithm.
Average Case Analysis of No Carry Adder: Addition in log_{2} n + O(1) Steps on Average: A Simple Analysis.

Thanks for reading.
Peace

hitch_hiker42 · December 21, 2019, 11:58am

Your solution was a bit messy to be honest, I’d a hard time following it (or it might be that it’s quite long (a year) since I’ve debugged a code written in C). First I tried lots of random (not truly random of course) test cases but your code passed them all (verified by testing them with mine). Then I tried to explicitly generate a test case which I initially thought was possible but which turned out to not exist : you cannot add two numbers of whose the longer has say, n-bits, and get a result with more than (n + 1)-bits. For that you need to pass a carry (well, because nothing else can be passed) two bits ahead of the MSB - and to do that you have to first pass that carry one bit ahead. Since passing is done by positions whose XOR value is 1 and the XOR value of bits ahead of MSB cannot be made 1 (you need exactly one set bit at a position to give an XOR of 1 there but there are none following the length of the bit-strings to the left) , hence you cannot pass carries past one after MSB (again, to the left). But what if you can make the XOR of the (MSB + 1)^th bit 1 at some point throughout the iterations? To do that, you need to pass a 1 to that position through a direct carry from MSB (AND at MSB equals 1) such that XOR at that position becomes 1 afterwards - and AND remains zero because of the same (XOR equals 1 implies AND equals zero for even number of bits in discourse). But that wouldn’t work because the two 1s at a position will act as a barrier and break the carry reaction that might propagate through here. See it anyway, you’re not going to get a number more than (n + 1)-bit long by adding two numbers such that the longer one (if not of same length) is n-bit long. All other cases are binary in nature (swidt?): ones which give you an (n+1)-bit number and ones which doesn’t. Everything else kind of has been spanned in this forum.

So after I did all that, I noticed that the solution is an AC one (didn’t know you solved the issue and changed the link back then). Congratulations anyway.

aman_3 · December 22, 2019, 4:51pm

code is already formatted.

striker22 · December 22, 2019, 6:10pm

@hitch_hiker42 Thanks for taking the time to analyze the program, actually there was small bug in my code, i.e for the case when A = 0 and B = 0, the code is giving the output 1 rather it should be 0, I fixed it and it was accepted.

Thanks for reading.
Peace

learner_sumit · December 27, 2019, 6:15pm

thanks for beautiful explanation.

rohan3299 · December 27, 2019, 6:37pm

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner s=new Scanner(System.in);
int t=s.nextInt();
while(t>0){
String a=s.next();
String b=s.next();
if(b.equals(“0”)){
System.out.println(0);
t–;
continue;
}
if(a.equals(“0”)){
System.out.println(1);
t–;
continue;
}
if(b.length()>a.length()){
int temp=b.length()-a.length();
while(temp!=0){
a=“0”+a;
temp–;
}
}
else if(b.length()<a.length()){
int temp=a.length()-b.length();
while(temp!=0){
b=“0”+b;
temp–;
}
}

	    int i=b.length()-1;
	    int max=Integer.MIN_VALUE;
	    int count=0;
	    while(i>=0){
	        if(a.charAt(i)=='1' && b.charAt(i)=='1'){
	            if(count==0){
	                count++;
	            }
	            else{
	                count++;
	                if(count>max){
	                    max=count;
	                }
	                count=1;
	            }
	        }
	        else if((a.charAt(i)=='1' && b.charAt(i)=='0')||(a.charAt(i)=='0' && b.charAt(i)=='1')){
	            if(count!=0){
	                count++;
	            }
	        }
	        else{
	            if(count!=0){
	                count++;
	                if(count>max){
	                    max=count;
	                }
	                count=0;
	            }
	        }
	        i--;
	    }
	    count++;
	    if(count>max){
	        max=count;
	    }
	    System.out.println(max);
	    t--;
	}
}

}

Can any1 tell me what is wrong in my code … All the test cases are running except the 3rd one??

striker22 · December 27, 2019, 9:21pm

@rohan3299 Format your code first as the forum software has messed it up, or give the solution link.

neel19 · December 31, 2019, 1:01pm

How did you get the idea??

hitch_hiker42 · December 31, 2019, 1:52pm

Simple: read a problem very carefully until every necessary detail is ingrained in your mind. Hold the horses of excitation for a while so that you don’t immediately start coding. In this ‘while’ that you’ve earned, get a pencil and a paper and list your initial observations and try to make sure (if necessary, prove) of the correctness of the algorithm you came up with (assuming you formulated an algorithm right after understanding the problem statement, that happens only with the easier ones or when you’ve been through a lot of practice).

In my case, I didn’t have a solution ready, so I had to work through some made-up examples in a careful manner so that I don’t miss something (well, I had sufficient free time because the holidays had already started). I had written some binary strings with some easier patterns first (like all bits set or reset in both – or one being the ones compliment of the other) and then somewhat random. I arranged the bits so that the positions were aligned (as when you do simple arithmetic) and simulated the given algorithm, cycle after cycle until it terminated. To be honest, I had recently revised digital electronics (for no good reason), so I kind of knew exactly what the algorithm was doing (full-adder and related stuff as mentioned in my first answer in this sub-forum). I soon found a pattern and claimed that everything we need is hidden in the first AND and XOR of the bit-strings. To be sure of the idea, I informally proved it. Now that the ‘while’ was over, I wanted the code to be sufficiently smooth so as to express the idea elegantly and neatly (without redundancy and overly clever tricks). Keeping that in mind, I closed the notebook and woke my laptop. I coded it and for a surprise, the first submission itself got AC (yea, awesome moment of glory)

neel19 · January 1, 2020, 1:10pm

Sorry for disturbing you again, What’s the role of this line
u = ‘0’ + u;
I didn’t get it.

roshanaji777 · January 2, 2020, 3:53am

What is this statement for?

vreauoxfordpls · January 6, 2020, 1:35pm

It’s not just you. The editorial code is wrong.

hitch_hiker42 · January 19, 2020, 12:50pm

To take care of the possible overflow.

pkslnct · January 28, 2020, 8:01am

Could anyone please explain to me the third point of the explanation : " Finally, if it’s equal to 3 then carrying process will start from scratch…and so on " with some example. Why there will be zero at ith place after first xor? I am getting hard time visualizing the whole process given in third point.

anon79442027 · August 12, 2021, 3:37pm

I did this problem in a different way.
what we have to do is to make the string B consisting of ‘0’ only, and then string A is the resultant string .

If the maximum of length of string A and B is n. then, the resultant string can have atmost (n+1) length.

In every iteration of while loop, I am choosing those bits ,which are set in both binary string, clear all those bits from string A and right shift all these bits by one place and this is our new string B.

so, first of all make the length of both of the string equal to n+1, by inserting zeroes from the beginning of strings.

I find the number of iteration of while loop, which will clear all the set bit in string B. and took maximum among those number of iteration, which is required answer.

Start from the most significant bit of original string B and for all the i from 1 to n in string B such that B[i]=‘1’,set B[i]=‘0’ find the j in string A such that j<=i, A[j]=‘0’ and j is maximum possible. set A[j]=‘1’,and for all x from j+1 to i, set A[x]=‘0’.
Take the maximum of (i-j+1) for all possible value of i, which is the answer.

At the end, we also have string A, which is the resultant string. and string B consisting of all zeroes.

Here is my code : CodeChef: Practical coding for everyone
Any suggestion /query are welcomed.