HackerEarth problem : number of occurrences of a number in the array

Question

I have written a solution to Memorise me problem on Hacker Earth but it takes a lot of memory space and time limit exceeds in the last test case.

The first line of input will contain \$N\$, an integer, which is the total number of numbers shown to your team.

The second line of input contains \$N\$ space separated integers.

The third line of input contains an integer \$Q\$, denoting the total number of integers.

The Next \$Q\$ lines will contain an integer denoting an integer, \$Bi\$, for which you have to print the number of occurrences of that number (\$Bi\$) in those \$N\$ numbers on a new line.

If the number \$Bi\$ isn’t present then print NOT PRESENT on a new line.

Constraints

\$1 \le N \le 105, 0 \le Bi \le 1000, 1 \le Q \le 1055\$

This is my code :

public static void main(String args[]) throws Exception {

    // BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String noOfElements = br.readLine();
    int n = Integer.parseInt(noOfElements);
    int i = 0;

    String[] numberArray = br.readLine().split(" ");

    String noOfQueries = br.readLine();
    int q = Integer.parseInt(noOfQueries);

    String[] queries = new String[q];

    for (i = 0; i < q; i++) {
        String query = br.readLine();
        String queryNumber = query.trim();
        queries[i] = queryNumber;
    }

    for (i = 0; i < queries.length; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (queries[i].equals(numberArray[j])) {
                count++;
            }
        }
        if (count == 0) {
            System.out.println("NOT PRESENT");
        } else {
            System.out.println(count);
        }
    }

}

Answer 1

Thanks for sharing the code!

IMHO this coding competitions are no good practices for coding style because they focus on fast "throw away" solutions. This means some of the following suggestions seam to be "over engeneered" but are essential for real live projects.

Naming

Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers. on the brite site you're following the Java Naming Conventions

Keep name and type aligned

You nave a variable noOfElements but it does not contain a number. It contains a String which is a bit surprizing to your readers.

But you have a variable n whch is a nuber type an holds the number value of the string stored in noOfElements.

Since you don't use noOfElements in your program anymore you could inline it and nrename n to noOfElements:

int noOfElements = Integer.parseInt(br.readLine());

Avoid single letter names

In Java the length of identifier names names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

Comments

Coments should express why the code is like it is. The comment you placed is meaningless since it just repeats the following code.

Single Responsibility / Same Level of Abstraction

You method has some distinct responsibilities:

• aquire input
• convert input into numbers
• convert input into arrays
• count occurrences
• output result

You should separate those responsibilities in separate methods.

Also any method should either do (primitive) calculations or call other methods, not both. Following this two principles yur main would change to something like this:

public static void main(String args[]) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] numberArray = aquireNumberArray(br);
    String[] queries = aquireNumbersToSearch(br);
    for(String number : queries){
       int countOfOccurrences = countOccurencesOf(number, numberArray);
       outputToConsole(countOfOccurrences);
    }          
}
private String[] aquireNumberArray(BufferedReader br){
    br.readLine(); // skip count of numbers
    return br.readLine().split(" ");
}
private String[] aquireNumbersToSearch(BufferedReader br){
    in numberOfQueries = convertToInt(br.readLine());
    return readNumbersToSearch(numberOfQueries, br);
}
// implementations of other methods used above

visibility scopes

You declare most of your variables at the top of the method.

You should not do this since some of this variables may belong to some code that's going to be moved to a new method and force the IDEs automated refactoring to introduce an unnessessary parameter to this new method.

Always declare variables at the place of their first use.

Answer 2

You can maintain a HashMap where key will be the number and value will be its frequency.