HackerEarth Girlfriend's Demand challenge, solved two ways

Question

I solved the Girlfriend's Demand challenge on HackerEarth. In summary:

Input: First line of the input contains a string S. Next line contains an integer Q, the number of queries. Each of the next Q lines contains a test case consisting of 2 integers, a and b.

Output: If S is repeated infinitely, would string positions a and b contain the same character (using 1-based indexing)? For each query, print “Yes” or “No”.

Constraints:

• 1 ≤ |S| ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 1 ≤ a, b ≤ 10¹⁸

Sample Input:

vgxgp 
3 
2 4 
2 5 
7 14 

Sample Output:

Yes 
No 
Yes

My first solution:

public static void main(String args[] ) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String item=br.readLine();

        StringBuffer sb=new StringBuffer();
        int len = item.length();
        int inputs = Integer.parseInt(br.readLine());

        while(inputs-->0)
        {
            String strarr[] =null;

                strarr = br.readLine().split(" ");

            long a=Long.parseLong(strarr[0]);
            long b=Long.parseLong(strarr[1]);
            a=a-1;
            b=b-1;
            a=a%len;
            b=b%len;

            if(item.charAt((int)a)==item.charAt((int)b))
                sb.append("Yes\n");
            else
                sb.append("No\n");


        }

        System.out.println(sb);


    }

While this gave me an output in almost 5.2954 seconds for various inputs, when I tried the same inputs on this version of the code that I wrote:

public static void main(String args[] ) throws Exception {
      BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
        String demanded=reader.readLine();
        int length = demanded.length();
        int T=Integer.parseInt(reader.readLine());
        for(int i = 0;i < T; i++){
            String[] pairedAAndB=reader.readLine().split(" ");
                long a = ((Long.parseLong(pairedAAndB[0]) - 1) % length);
                long b = ((Long.parseLong(pairedAAndB[1]) -1) %length);
            System.out.println((demanded.charAt((int)a)==demanded.charAt((int)b)) ? "Yes" : "No");

    }

}

It took around 15.7819 seconds. What is the best way to convert long to int optimally? What I'm not able to understand is why the second code snippet is taking so much time when the second version is almost similar. There must be something about the second version that I'm not able to understand.

Answer 1

Slowness caused by System.out.println

The difference between the first and second programs isn't the parsing or long/int conversion. The difference is that in the first program, you use a StringBuffer to build your output into one big string (which is good). In the second program, you call System.out.println() for each of your 100000 lines of output. This takes a significant amount of time.

The current code

I don't see any problem with your first program. It runs about as well as can be expected. There are some strange indentations in your code and a few places where I would have added some spaces, but otherwise I don't see other problems. I played around with it and got it to run about 8% faster by changing the parsing, but it wasn't really significant. For your reference, here is the modified code:

public static void main(String args[] ) throws Exception {
    BufferedReader br        = new BufferedReader(
                                    new InputStreamReader(System.in));
    String         item      = br.readLine();
    int            len       = item.length();
    int            numInputs = Integer.parseInt(br.readLine());
    StringBuffer   output    = new StringBuffer(numInputs * 4);

    while (numInputs-- > 0) {
        String line  = br.readLine();
        int    space = line.indexOf(' ');
        long   a     = Long.parseLong(line.substring(0, space-1));
        long   b     = Long.parseLong(line.substring(space+1));

        a = (a-1) % len;
        b = (b-1) % len;

        if (item.charAt((int)a) == item.charAt((int)b))
            output.append("Yes\n");
        else
            output.append("No\n");
    }

    System.out.println(output);
}

Answer 2

Both solutions are pretty good, but there are minor improvements to be made.

Declaring throws Exception is mysterious: it leaves me wondering what kinds of errors might be lurking in the code. If you need IOException, then declare just that.

Since you want to read numbers, the code would look nicer with a java.util.Scanner instead of a BufferedReader.

You can use a StringBuilder instead of a StringBuffer, since your code isn't multithreaded. Estimating the required buffer size is a good idea for performance.

Instead of inventing new notation like T, either stick with the notation used in the challenge (like Q) or use descriptive variable names (like demanded).

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
        String s = scanner.nextLine();
        int length = s.length();

        int q = scanner.nextInt();
        StringBuilder output = new StringBuilder(q * "Yes\n".length());

        while (q-- > 0) {
            int a = (int)((scanner.nextLong() - 1) % length),
                b = (int)((scanner.nextLong() - 1) % length);
            output.append(s.charAt(a) == s.charAt(b) ? "Yes\n" : "No\n");
        }
        System.out.print(output);
    }
}