2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ your result needs some refactoring if you want other to read it. \$\endgroup\$ – tuergeist Feb 22 '12 at 12:49
  • 3
    \$\begingroup\$ 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? \$\endgroup\$ – Aasmund Eldhuset Feb 22 '12 at 21:31
  • \$\begingroup\$ please add "homework" flag \$\endgroup\$ – tuergeist Feb 23 '12 at 7:32
9
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy