CODEWITHSUNDEEP
javagraph
anna
anna

Reputation: 433

Checking if the graph exist (java)

Determine whether there exists a graph with a sequence of degrees of vertices (s = s1, s2...sn). What is the best and most optimized algorithm for solving this problem.

 Input:
    the first line contains `t<100` - amount of sequnces.
    the second line contains value `n <= 1000000`(length of a sequence).
    the third line contains  contains `n` non-negative integer numbers. And so on.
Output:
    if the graph can exist print "yes" otherwise print "no".
For example: 
Input:
3
5
1 2 3 2 1
4
3 3 2 2
3
1 3 2
Output:
No
Yes
Yes

The maximum execution time should be 0.4 second. Here is my code (If the number of odd vertices is even, then the graph exists):

    import java.util.Scanner;
public class Main {
      public static final Scanner in = new Scanner(System.in);
    public static void isGraph (int []a, int n) {
        int k=0;
        for(int i=0; i< n; i++) {
            if(a[i] %2 != 0) {
                k++;
            }
        }
        if(k%2 == 0)
           System.out.println("Yes");
        else
            System.out.println("No");

    }
    public static void main(String[] args) throws Exception{
        double t1 = System.nanoTime();
        int n;
        int []a;
        int t = Integer.parseInt(in.nextLine());
        while(t-- > 0) {
            n = in.nextInt();
            a = new int[n];
            for(int i=0; i<n; i++)
                a[i] = in.nextInt();
            isGraph(a,n);
        }
        System.out.println(System.nanoTime() - t1);
    }
}

But the execution time of this program is more than 0.4 second. I get run time exceeded. How I can optimize code and speed up runtime. May be there is another algorithm to solve this task, please help me.

Upvotes: 1

Views: 195

Answers (2)

Ian Mc
Ian Mc

Reputation: 5829

I think I have a faster way for you. Please verify this. If you are concerned about the final outcome of even/odd, then there seems to be no reason to keep track of the k counter. You can keep a dynamic value of whether the running sequence is even or odd:

public static void isGraph (int []a, int n) {
    int k = 0;
    for(int i=0; i< n; i++) {
        k += a[i] & 1;
    }
    if(k%2 == 0)
        System.out.println("Yes");
    else
        System.out.println("No");

}

This might help your reading: I have no experience with it however, I got it from a competition website:

Slow way to read:

/** Read count integers using Scanner */
static int scanInteger(int count) {
    Scanner scanner = new Scanner(input);
    int last = 0;
    while (count-- > 0) {
        last = scanner.nextInt();
    }
    return last;
 }

Faster way:

static int readIntegers(int count) 
    throws IOException {
    BufferedReader reader = new BufferedReader(
           new InputStreamReader(input) );
    StringTokenizer tokenizer = new StringTokenizer("");
    int last = 0;
    while (count-- > 0) {
        if (! tokenizer.hasMoreTokens() ) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        last = Integer.parseInt(tokenizer.nextToken());
    }
    return last;
}

EDIT: to show how to avoid two phases where Phase 1 is the read loop, and Phase 2 is the algorithm:

public static void main(String[] args) throws Exception{
    double t1 = System.nanoTime();
    int n;
    // int []a;  //  Not necessary
    int t = Integer.parseInt(in.nextLine());
    while(t-- > 0) {
        n = in.nextInt();
        // a = new int[n];  // Not necessary
        int k = 0;
        int a;
        for(int i=0; i<n; i++) {
            a = in.nextInt();
            k += a & 1;
        }
        // isGraph(a,n);  // Not necessary
        if(k % 2 == 0)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
    System.out.println(System.nanoTime() - t1);
}

Upvotes: 2

Stephen C
Stephen C

Reputation: 718826

May be there is another algorithm to solve this task

That's not the problem (IMO).

Hint 1: since you know the length of the sequence beforehand, you can create the array and parse the sequence faster than this:

  a = Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();

(Java 8+ streams are elegant, but they are not the fastest way.)

Hint 2: using Scanner is probably faster than reading strings and parsing them.

Hint 3: you could probably avoid creating an array entirely. (It would be poor coding practice IMO ... but if performance is critical ...)

Upvotes: 0

Related Questions