Too much execution time

[Yohan Weerasinghe]

Hi,

Following is a complete question I copied from a site

The purpose of this problem is to verify whether the method you are using to read input data is sufficiently fast to handle problems branded with the enormous Input/Output warning. You are expected to be able to process at least 2.5MB of input data per second at runtime.
Input

The input begins with two positive integers n k (n, k<=107). The next n lines of input contain one positive integer ti, not greater than 109, each.
Output

Write a single integer to output, denoting how many integers ti are divisible by k.
Example

Input:
7 3
1
51
966369
7
9
999996
11

Output:
4

OK. For the question these are the restrictions

Time limit: 8s
Source limit: 50000

And the following is my code

import java.io.*;
import java.util.*;

public class EI
{
    
    
    public static void main(String[]args)throws IOException
    {
        int n=1,k=0,t=0,answer=0,division=0;
        String holder=null;
        Scanner  scan=null;
        
        BufferedReader   br = new BufferedReader(new InputStreamReader(System.in));
        
        holder = br.readLine();
        scan = new Scanner(holder);
        
         n = scan.nextInt();
         k = scan.nextInt();
         
         if(k>10000000)
         {
             System.out.println("Invalid Input");
             return;
         }
         
        
            for(int a=0;a<n;a++)
            {
             
                
                    holder = br.readLine();
                    scan = new Scanner(holder);
                    t = scan.nextInt();
                    
                    if(t>1000000000)
                    {
                        System.out.println("Invalid Input");
                        break;
                    }
                    else
                    {
                        division = t%k;
                        
                        if(division>0)
                        {
                           
                        }
                        else if(division==0)
                        {
                            answer++;
                        }
                    }
                       
                }
              System.out.println("The answer is: "+answer);
            }
    
}

Whenever I run this code in that site, it says "Time Limit Exceeded". Is there is a way to reduce the performance time and get rid of that problem? Please help..

[John Jai]

Your code seems to contradict your statement of "Time Limit Exceeded" - where it is present at first place? Have you posted the wrong code.

One thing I find is that a single scanner can be used throughout.

import java.util.Scanner;

public class EI {

	public static void main(String[]args)	{
		
		int n=1,k=0,t=0,answer=0,division=0;
		
		final Scanner scan = new Scanner(System.in);
		
		if (scan.hasNextInt()){
			n = scan.nextInt();			
		}
		if (scan.hasNextInt()){
			k = scan.nextInt();
		}

		if(k>10000000)
		{
			System.out.println("Invalid Input");
			return;
		}
		
		for(int a=0;a<n;a++)
		{			
			t = scan.nextInt();
			
			if(t>1000000000)
			{
				System.out.println("Invalid Input");
				break;
			}
			else
			{
				division = t%k;

				if(division>0)
				{

				}
				else if(division==0)
				{
					answer++;
				}
			}

		}
		System.out.println("The answer is: "+answer);
	}
}

Moderator - kindly move this to Beginning Java forum if its more appropriate

[Joanne Neal]

What is the purpose of lines 46 - 49 (or 37 - 40 in John's code) ? Getting rid of them will probably only save microseconds on each loop, but every little helps.

Also reducing the scope of the division variable may allow the compiler to optimise that bit of the code.

[Winston Gutkowski]

Yohan Weerasinghe wrote:Whenever I run this code in that site, it says "Time Limit Exceeded". Is there is a way to reduce the performance time and get rid of that problem? Please help..

Well personally, I like your choice of a BufferedReader and readLine() for reading the lines; I suspect it's quite a bit quicker than Scanner.
And you certainly don't need to scan the String: I'd use String.split() for the header and a simple Integer.parseInt() for your 'ti' lines.

Winston

[Yohan Weerasinghe]

Hi guys, Thanks a lot for all of your replies. I didn't get any email notification for this thread, that is why I got late to reply. I will check your suggestions, meanwhile, I am talking about this problem

http://www.codechef.com/problems/INTEST

[Yohan Weerasinghe]

I tried John's code. But still the same. Now going to try Winstan's suggestion.

[Yohan Weerasinghe]

Joanne Neal wrote:

Also reducing the scope of the division variable may allow the compiler to optimise that bit of the code.

errr..I didn't understand. You mean Class Cope Variables or something? Or reducing the Value of it? If it is value, I am afraid I can't because that what they have given