Strange algorithm results I came across this thread and I am working on the same problem. My best algorithm passes 6/11 cases while the algorithm in the other thread does indeed pass 8/11 cases. Running time trials with random input my algorithm is significantly quicker (8 to 12 times depending on input) then the one in the other thread. So I am pretty confused on these results. 

I came across this thread and I am working on the same problem. My best algorithm passes 6/11 cases while the algorithm in the other thread does indeed pass 8/11 cases. Running time trials with random input my algorithm is significantly quicker (8 to 12 times depending on input) then the one in the other thread. So I am pretty confused on these results. 

Aside from empirical testing these are the reasons I think my code should be running better than the other implementation for these reasons.


Appending to a StringBuilder and printing once should be more
efficient than multiple print statements.
Better reduction in logic for binary addition. As well doing addition
from the bit index’s least significant 0 in both BitSets, a and b,
reduces unnecessary computation. 
Using BufferedReader has a lot less overhead than using Scanner.
BitSet really didn’t offer much difference in the terms of
performance than a character array but reversing the binary strings
is a waste and the StringBuilder reverse is not the best
performance.


Can anyone shed some light onto why the seemingly slower algorithm does better in the testing?

Version 2

private static String floatSum()
{
    final Scanner input = new Scanner(System.in);
    final int number_bits = input.nextInt();
    final int number_queries = input.nextInt();
    final StringBuilder builder = new StringBuilder();  
    final char[] a = new StringBuilder(input.next()).reverse().toString().toCharArray();
    final char[] b = new StringBuilder(input.next()).reverse().toString().toCharArray();

    for(int queries = 0; queries &lt; number_queries; queries++)
    {
        switch(input.next().charAt(4))
        {
            case 'a':
                a[input.nextInt()] = input.next().charAt(0);    
                break;
            case 'b':
                b[input.nextInt()] = input.next().charAt(0);    
                break;      
            default:
                final int index = input.nextInt();

                int carry_bit = 0;

                for(int iter = index - 1; iter &gt;= 0; iter--)
                {
                    if(a[iter] == b[iter])
                    {
                        carry_bit = a[iter] - 48;
                        break;
                    }
                }

                builder.append(index == number_bits ? carry_bit : ((a[index] - 48) + (b[index] - 48) + carry_bit) % 2);     
                break;
        }

    }

    return builder.toString();
}
Consider this case:

A: 1111111111
B: 1111111111
Query: n+1


The other post terminates very quckly. It knows that since both numbers end in 1, it must carry and thus doesn't have to scan throughout the entire string. On the other hand, your method tries to find clear bits but since there aren't any, it ends up going through the whole bitstring.

Probably, yours is faster over all, but this pathological case happens to have been put first in the test cases and so your program fails.

                if(carry &amp;&amp; a.get(iter) &amp;&amp; b.get(iter))
                {
                    carry = true;
                    value = 1;
                }
                else if((carry &amp;&amp; a.get(iter)) || (carry &amp;&amp; b.get(iter))  || (a.get(iter) &amp;&amp; b.get(iter)))
                {
                    carry = true;   
                    value = 0;
                }
                else if(carry || a.get(iter) || b.get(iter))
                {
                    carry = false;
                    value = 1;
                }
                else
                {
                    carry = false;      
                    value = 0;
                }


This whole bit kinda hard to follow you could instead do something like:

int bits = a.get(iter) ? 1 : 0 + b.get(iter) ? 1 : 0 + carry ? 1 : 0;
value = bits % 2;
carry = bits / 2;


I think its a clearer

                int a_index = a.nextClearBit(number_bits - index);
                int b_index = b.nextClearBit(number_bits - index);


Yeah, not gonna fly. nextClearBit has to scan through the bitset bit by bit in order to do that. You are gonna need to come up with a way to look through the bits without looking at each individual bit. I've solved this problem, and I used a specialized data structure to do it.