CODEWITHSUNDEEP
javaperformance
johny655
johny655

Reputation: 25

HackerEarth exercise running out of time

I solved the following problem from HackerEarth. All test cases are correct except the last one bacause it runs out of time. I tried optimizing my solution but I cannot optimize it better. Here is my solution:

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class TestClass {

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        Set<Integer> perfectNumbers = new HashSet<>();
        for (int i = 0; i <= 20; i++) {
            perfectNumbers.add(i * i * i);
        }
        for (int i = 1; i <= 44; i++) {
            perfectNumbers.add(i * i);
        }

        int t = sc.nextInt();
        for (int k = 0; k < t; k++) {
            int db = 0;
            int n = sc.nextInt();
            int[] a = new int[1001];
            int[] b = new int[1001];
            int[] numbers = new int[n];
            for (int j = 0; j < n; j++) {
                int x = sc.nextInt();
                numbers[j] = x;
                for (Integer perfect : perfectNumbers) {
                    if (x == perfect - x) {
                        b[x]++;
                    } else if (perfect - x >= 0 && perfect - x <= 1000)
                        a[perfect - x]++;
                }
            }
            for (int j = 0; j < n; j++) {
                db += a[numbers[j]];
            }
            for (int j = 0; j <= 1000; j++) {
                if (b[j] > 1) {
                    db += b[j] * (b[j] - 1);
                }
            }

            System.out.println(db / 2);           
        }
    }
}

Upvotes: 1

Views: 733

Answers (1)

Csa77
Csa77

Reputation: 697

Probably you should consider reading the input with some faster method because Scanner is really slow. You could for example wrap Scanner into a BufferedReader.
I modified the code. Now it passes all test cases: 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

class TestClass {

    public static void main(String args[]) throws Exception {
        FastReader sc = new FastReader();
        Set<Integer> perfectNumbers = new HashSet<>();
        for (int i = 0; i <= 20; i++) {
            perfectNumbers.add(i * i * i);
        }
        for (int i = 1; i <= 44; i++) {
            perfectNumbers.add(i * i);
        }

        int t = sc.nextInt();
        for (int k = 0; k < t; k++) {
            int db = 0;
            int n = sc.nextInt();
            int[] a = new int[1001];
            int[] b = new int[1001];
            int[] numbers = new int[n];
            for (int j = 0; j < n; j++) {
                int x = sc.nextInt();
                numbers[j] = x;
                for (Integer perfect : perfectNumbers) {
                    if (x == perfect - x) {
                        b[x]++;
                    } else if (perfect - x >= 0 && perfect - x <= 1000)
                        a[perfect - x]++;
                }
            }
            for (int j = 0; j < n; j++) {
                db += a[numbers[j]];
            }
            for (int j = 0; j <= 1000; j++) {
                if (b[j] > 1) {
                    db += b[j] * (b[j] - 1);
                }
            }
            System.out.println(db / 2);
        }
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            Integer nr=null;
            try {
                nr = Integer.parseInt(next());
            } catch (Exception e) {
                //something went wrong
            }
            return nr;
        }


    }

}

Upvotes: 2

Related Questions