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.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;
public class ChangingBits 
{
 public static void main(final String... the_args) throws IOException 
 { 
 System.out.println(floatSum());
 }
 
 private static BitSet buildBitSet(final String the_string)
 {
 final BitSet bits = new BitSet();
 
 for(int iter = 0; iter < the_string.length(); iter++)
 {
 if(the_string.charAt(iter) == '1')
  {
 bits.set(iter);
 }
 }
 
 return bits;
 }
 
 private static String floatSum() throws IOException
{
 final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 final String parameters = input.readLine();
 final int white_space = parameters.indexOf(' ');
 final int number_bits = Integer.parseInt(parameters.substring(0, white_space));
 final int number_queries = Integer.parseInt(parameters.substring(white_space + 1));
 final StringBuilder builder = new StringBuilder(); 
 final BitSet a = buildBitSet(input.readLine());
 final BitSet b = buildBitSet(input.readLine());

 for(int queries = 0; queries < number_queries; queries++)
 {
 final String input_query = input.readLine();
 switch(input_query.charAt(4))
 {
 case 'a':
 a.set(number_bits - 1 - Integer.parseInt(input_query.substring(6, input_query.length() - 2)), input_query.charAt(input_query.length() - 1) == '1'); 
 break;
 case 'b':
 b.set(number_bits - 1 - Integer.parseInt(input_query.substring(6, input_query.length() - 2)), input_query.charAt(input_query.length() - 1) == '1'); 
 break; 
 default:
 final int index = Integer.parseInt(input_query.substring(6, input_query.length()));
 int offset = number_bits - 1;
 int value = 0;
 boolean carry = false;

 if(index < number_bits)
 {
 int a_index = a.nextClearBit(number_bits - index);
  int b_index = b.nextClearBit(number_bits - index);
 
  while(a_index != -1 && b_index != -1)
 {
 if(a_index == b_index)
 { 
 offset = a_index;
 break;
 }
  else if(a_index < b_index)
 {
 a_index = a.nextClearBit(a_index + 1);
  }
 else if(a_index > b_index)
  {
 b_index = b.nextClearBit(b_index + 1);
 }
 }
 }

 for(int iter = offset; iter >= Math.max(number_bits - index - 1, 0); iter--)
 { 
 if(carry && a.get(iter) && b.get(iter))
 {
 carry = true;
 value = 1;
 }
 else if((carry && a.get(iter)) || (carry && b.get(iter)) || (a.get(iter) && 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;
 }
 }
 if(index == number_bits)
 {
 value = carry ? 1 : 0;
 }
  builder.append(value);
 break;
 }
 }
 return builder.toString();
 } 
}

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