Time limit exceded in simple java program

fastinputoutput
java
javalearning
time-limit
voters

#1

guys my simple java program when i submitted for problem link here for problem VOTERS gives time limit exceeded error.though i am not so much aware of faster input in java program please suggest me some tips and Examples for faster input in a java program. my submitted code is here click here for submitted solution (which is time limit exceeded)
please help me…thanks.

//import java.io.*;
import java.lang.*;
import java.util.*;
class Main
{
public static void main(String args[])
{
int i;
HashSet set1=new HashSet ();
HashSet set2=new HashSet ();
HashSet set3=new HashSet ();
HashSet result=new HashSet ();
Iterator iterator;
Scanner sc=new Scanner(System.in);
//BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
try{
int m=sc.nextInt();
int n=sc.nextInt();
int p=sc.nextInt();
for(i=0;i<m;i++)
{
int k=sc.nextInt();
set1.add(k);
}
for(i=0;i<n;i++)
{
int k=sc.nextInt();
set2.add(k);
}
for(i=0;i<p;i++)
{
int k=sc.nextInt();
set3.add(k);
}}catch(Exception e){}
 
for(iterator=set1.iterator();iterator.hasNext();)
{
Object k=iterator.next();
if(set2.contains(k)|set3.contains(k))
result.add(k);
}
for(iterator=set2.iterator();iterator.hasNext();)
{
Object k=iterator.next();
if(set1.contains(k)|set3.contains(k))
result.add(k);
}
 
System.out.println(result.size());
TreeSet result1=new TreeSet(result);
for(iterator=result1.iterator();iterator.hasNext();)
{
System.out.println(iterator.next());
}
}
}

#2

Here is an example how to do it faster - Scanner is too slow, use BufferedReader :wink: Hope that helps.


#3

@ajay154 : There are many issues with your code , which will make it fail time limit .

  1. As pointed by @betlista , don’t use Scanner use BufferedReader . The way to use it is ,
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    This reads a line of input . If the line contains 3 elements , then write .
    int blank = str.indexOf(" “);
    int one = Integer.parseInt(str.substring(0,blank));
    str = str.substring(blank+1);
    blank = str.indexOf(” ");
    int two = Integer.parseInt(str.substring(O,blank));
    int three = Integer.parseInt(str.substring(blank+1));
    If the line contains only one element , write
    int num = Integer.parseInt(str);
  2. As pointed by @junior94 , dont use system.out.print… as it flushes the output every time it is called . Use BufferedOutputStream.
    BufferedOutputStream bos = new BufferedOutputStream(System.out);
    When you have to output something change it to string and then byte array .
    Like , bos.write(new Integer(result).toString().getBytes());
    In the end once when your program exits , write bos.flush() , otherwise you will not see any output .
    To print end of line , write
    String eol = System.getProperty(“line.separator”);
    byte[] eolb = eol.getBytes() ;
    Write these two lines once in beginning .
    and when you have to end a line of output , write : bos.write(eolb);
  3. The data structures you have used are suspect . They may not give the best performance for this problem . Note that input is already sorted in all three lists . Iterate these three lists simultaneously . Look at the current minimum and see if it is at the iteration point of more than one list or not . Then move the iteration point of those lists which had the minimum and store the number in result list if it was in majority . This way the result list will be generated in sorted manner by itself .

#4

#5

Also if you are printing a lot of sutff, like in a loop, you should avoid using System.out object, instead use some Writer object like BufferedWriter


#6

thanks but can you clarify with more examples in which BufferedReader is used.


#7

thanks @vineetpaliwal …its clarify my doubt…i will use it


#8

@vineetpaliwal your answer is correct but I think the best way to read integers using BufferedReader is to read a line and break it into tokens like:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int one = Integer.parseInt(st.nextToken());
int two = Integer.parseInt(st.nextToken());

and so on…

Note: I said the best way considering simplicity and time taken to read…


#9

Sorry for late comment, I’ll recommend @junior94’s comment for @vineetpaliwal’s answer.


#10

Also using Writer is not necessary, it’s a lot simpler to use StringBuilder to collect data I want to print a then simply call System.out.println() once or once for test case. StringBuilder has nice method setLength() for “erasing” data from it, so at the end of test case you simply call setLength(0) and you do not need to create new instance :wink:

StringBuilder buff = new StringBuilder()
foreach test case
    // ... some computation
    buff.append(result).append( '

’ );
System.out.println( buff.toString() );
buff.setLength(0);


#11

yes the method i described was for reading 2,3 integers in a single line . If there are more integers in a single line , then i use a different snippet of code . Anyways , somethings are a matter of choice too . Yes StringBuilder can also be used .