Problem
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<=idxInput
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 5Sample 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?
Solution
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