Changing bits in given big strings

Question

I came up with this question.

Let A and B be two N bit numbers. You are given initial values for A and B, and you should write a program which processes three kinds of queries:

set_a idx x: Set A[idx] to x, where 0 <= idx < N (where A[idx] is idx'th least significant bit of A.)
set_b idx x: Set B[idx] to x, where 0 <= idx < N.
get_c idx: Print C[idx], where C=A+B, and 0<=idx

Input

First line of input contains two integers N and Q consecutively (1 <= N <= 100000, 1<= Q <= 500000). Second line is an N-bit binary number which denotes initial value of A, and the third line is an N-bit binary number denoting initial value of B. Q lines follow, each containing a query as d escribed above.

Output

For each query of the type get_c, output a single digit 0 or 1. Output must be placed in a single line.

Sample Input

5 5
00000
11111
set_a 0 1
get_c 5
get_c 1
set_b 2 0
get_c 5

Sample Output

100

I solved this question on my own, but it is only passing 8 of 11 test cases. The remaining three exceed the time limit, which in Java is maximum 5 sec.

Here is my implementation:

import java.io.*;
import java.util.*;
class Solution {
public static void main(String args[]){
 int n, q, i;
 String ch;
 Scanner scanner = new Scanner(System.in);
 n = scanner.nextInt();
 q = scanner.nextInt();
 StringBuffer aa = new StringBuffer(scanner.next());
 StringBuffer bb = new StringBuffer(scanner.next());
 Solution sss = new Solution();
 aa.reverse();
 bb.reverse();
 char[] a = new char[n];
 char[] b = new char[n];
 aa.getChars(0, n, a, 0);
 bb.getChars(0, n, b, 0);
 for (i = 0; i < q; i++) {
 int id;
 char x;
 ch = scanner.next();
 if (ch.equals("set_a")) {
 id = scanner.nextInt();
 x = scanner.next().charAt(0);
 a[id] = x;
 } else if (ch.equals("set_b")) {
 id = scanner.nextInt();
 x = scanner.next().charAt(0);
 b[id] = x;
 } else if (ch.equals("get_c")) {
 id = scanner.nextInt();
 sss.out(a, b, id, n);
 }
 }
}
public static void out(char[] A, char[] B, int idx, int n) {
 if (idx == 0) {
 if ((A[idx] == '0' && B[idx] == '1') || (A[idx] == '1' && B[idx] == '0')) {
 System.out.print("1");
 } else if (A[idx] == '1' && B[idx] == '1') {
 System.out.print("0");
 } else if (A[idx] == '0' && B[idx] == '0') {
 System.out.print("0");
 }
 } else if (idx == n) {
 if (A[idx - 1] == '1' && B[idx - 1] == '1') {
 System.out.print("1");
 } else if (A[idx - 1] == '0' && B[idx - 1] == '0') {
 System.out.print("0");
 } else if ((A[idx - 1] == '0' && B[idx - 1] == '1') || (A[idx - 1] == '1' && B[idx - 1] == '0')) {
 int k = idx - 2;
 while (k >= -1) {
 if (k == -1) {
 System.out.print("0");
 break;
 }
 if (A[k] == '0' && B[k] == '0') {
 System.out.print("0");
 break;
 }
 if (A[k] == '1' && B[k] == '1') {
 System.out.print("1");
 break;
 }
 if ((A[k] == '0' && B[k] == '1') || (A[k] == '1' && B[k] == '0')) {
 k--;
 }
 }
 }
 } else if (idx > 0 || idx < n) {
 if (A[idx] == '0' && B[idx] == '0') {
 int k = idx - 1;
 while (k >= -1) {
 if (k == -1) {
 System.out.print("0");
 break;
 }
 if (A[k] == '0' && B[k] == '0') {
 System.out.print("0");
 break;
 }
 if (A[k] == '1' && B[k] == '1') {
 System.out.print("1");
 break;
 }
 if ((A[k] == '0' && B[k] == '1') || (A[k] == '1' && B[k] == '0')) {
 k--;
 }
 }
 } else if (A[idx] == '1' && B[idx] == '1') {
 int k = idx - 1;
 while (k >= -1) {
 if (k == -1) {
 System.out.print("0");
 break;
 }
 if (A[k] == '0' && B[k] == '0') {
 System.out.print("0");
 break;
 }
 if (A[k] == '1' && B[k] == '1') {
 System.out.print("1");
 break;
 }
 if ((A[k] == '0' && B[k] == '1') || (A[k] == '1' && B[k] == '0')) {
 k--;
 }
 }
 } else if ((A[idx] == '0' && B[idx] == '1') || (A[idx] == '1' && B[idx] == '0')) {
 int k = idx - 1;
 while (k >= -1) {
 if (k == -1) {
 System.out.print("1");
 break;
 }
 if (A[k] == '0' && B[k] == '0') {
 System.out.print("1");
 break;
 }
 if (A[k] == '1' && B[k] == '1') {
 System.out.print("0");
 break;
 }
 if ((A[k] == '0' && B[k] == '1') || (A[k] == '1' && B[k] == '0')) {
 k--;
 }
 }
 }
 }
}
}

How can I improve the execution speed of this code?

• tuergeist: your result needs some refactoring if you want other to read it.
• Aasmund Eldhuset: Based on the clear problem statement (that is divided into input/output/example sections) and the presence of a time limit and test cases, this is obviously a task from a programming contest or from an algorithms course - so why do you say "I came up with this question"? Are you allowed to ask other people for help in this contest?
• tuergeist: please add "homework" flag

Answer 1

Don't use arrays as representation for binary numbers. BitSet could save you a lot of work.

Except from that, your code is very repetitive. An example:

 if ((A[idx] == '0' && B[idx] == '1') || (A[idx] == '1' && B[idx] == '0')) {
 System.out.print("1");
 } else if (A[idx] == '1' && B[idx] == '1') {
 System.out.print("0");
 } else if (A[idx] == '0' && B[idx] == '0') {
 System.out.print("0");
 }

This could be written as:

 System.out.print(A[idx] == B[idx] ? "0" : "1");

So try to condense your logic as much as possible (as long as it stays readable). Learn about the laws of logic (e.g. de Morgan's rule).

I think you could improve speed by collecting bigger chunks of output in a StringBuilder, instead of spitting out single chars one by one.

Last but not least, follow good coding practices:

• follow Java's naming conventions (e.g. variables start always lower case)
• Single Responsibility Principle ("SRP"): Every method should have only one clearly defined job. This leads to short, reusable methods.
• Don't repeat yourself ("DRY"), try hard to factor out all code duplications