I using bit manipulation but it isn't quick enough? Is it because of Scanner class?

Question

This is the Question:

https://practice.geeksforgeeks.org/problems/find-the-odd-occurence/0

Given an array of positive integers where all numbers occur even number of times except one number which occurs odd number of times. Find the number.

Input can range from

1 ≤ T ≤ 100 : Test Cases
1 ≤ N ≤ 107 : Number of inputs
1 ≤ A[i] ≤ 106 : Inputs

Example:

Input:

1
5
8 4 4 8 23

Output:

23

This is code:

class GFG
 {
    public static void main (String[] args)
     {
     //code
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
              int N = sc.nextInt();
              int count = 0;
              for(int j = 0; j<N; j++){
                  int in = sc.nextInt();
                 count =count^in;
              }
              System.out.println(count);
        }

    }
}

My question is, The OJ took 2.5s to execute it and other people did this in significantly less time than mine. Some did it in 0.3s. And that too including inputting the numbers in an array and then iterating through them.

Why is that, Is this because of OJ or what, I didn't get it? Also I did the submission several times just to make sure there if there was a fault but all the time it took more than 2.5s.

score 3 · Accepted Answer · answered Nov 08 '19 at 04:07

Modern Java is considered quite fast, if you write optimised code, but it is still slower than languages which interact at a even lower level and have a ahead-of-time compiler. Anyways this topic has a very nice elaborated answer here : Is Java really slow?.

However your java code can still be optimised by using BufferedReader instead of directly using Scanner. Scanner actually takes a input stream and then parses according to the datatype we try to fetch, but BufferedReader just gives you a raw input and does no operations. Hence if you use it and parse your raw input line separately, it will be much better for your code runtime. I was able to get 0.61s with slightly modified version of your code using BufferedReader :

import java.util.*;
import java.io.*;
class gfg
{
    public static void main(String args []) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out, true);
        int t=Integer.parseInt(br.readLine());
        while(t-->0)
        {
            int N = Integer.parseInt(br.readLine());
            String str[]=br.readLine().split(" ");
            int count = 0;
            for(int j = 0; j<N; j++){
                int in = Integer.parseInt(str[j]);
                count =count^in;
              }
              System.out.println(count);
        }

    }
}

I think with some more optimizations you can probably, bring the time almost comparable to 0.3s.

This is the right answer; `Scanner` is often just too slow for competitive programming challenges, so +1. As an alternative to BufferedReader, consider using a fast IO library which is designed for competitive programming, such as this one https://github.com/sagar-rathod/Fast-Java-Input-Output/blob/master/Fast%20Java%20IO/src/com/sagarrathod/fastio/BufferInput.java . You can use it like a `Scanner`, because it has `nextInt` and so on, but it's much faster because it just assumes the input is valid (so there's no error-checks). That's a safe assumption in competitive programming challenges. — kaya3, Nov 11 '19 at 20:07

I using bit manipulation but it isn't quick enough? Is it because of Scanner class?

1 Answers1