javaalgorithmruntime-error

Unexplained RunTimeError while finding pairs in list of integers, whos sum is divisible by third integer


As preparation for a technical interview, I was practicing Java problems on a platform for this specific purpose. This platform has a number of visible or hidden test cases, my solution passes all test cases with the exception of two of the five hidden cases. When executing these cases the platform indicates a "runtime exception has occurred" but provides no additional information.

My question is: what possible runtime exceptions can you spot in my code?

Problem statement

The problem I was given was roughly as follows:

Given a (possibly non-unique) list of positive integers nums and a positive integer divisor, find the number of combinations of two different indices i < j, such that nums[i] + nums[j] is divisible by divisor.

Additional constraints:

1 ≤ nums.length ≤ 10^5
1 ≤ nums[i] ≤ 10^9
1 ≤ divisor ≤ 10^9
Memory usage: 1GB
Runtime: 3 minutes

My solution

I created the following solution to minimize the runtime:

long solution(int[] nums, int divisor) {
    long result = 0;
    int[] remainderCount = new int[divisor];
    Arrays.fill(remainderCount, 0);
    for(int i = 0; i < nums.length; i++) {
        int r = nums[i] % divisor;
        if(r > 0) {
            result += remainderCount[divisor - r];
        } else {
            result += remainderCount[0];
        }
        remainderCount[r] += 1;
    }
    return result;
}

So to summarize, I am trying to figure out what possible issues could be occurring with my code and how can I prevent them or optimize the solution to not include these pitfalls?

I've spent some time trying to reproduce the error by creating input data based on the constraints, however the program never runs into an issue. I've also looked into a number of RuntimeExceptions such as: ArithmeticException, NullPointerException, ClassCastException, ArrayIndexOutOfBoundsException,NegativeArraySizeException, ArrayStoreException, UnsupportedOperationException, NoSuchElementException but to me they all seem very unlikely given the constraints of the input. I can not understand this, so any and all pointers are very welcome! Thanks in advance :))


Solution

  • If nums is null, you will get a NullPointerException.

    If divisor is less than zero, you will get a NegativeArraySizeException.

    If divisor is zero, you might think that nums[i] % divisor would give an ArithmeticException. However, a closer examination shows that if divisor is zero, you won't execute the loop body.


    ... and how can I prevent them or optimize the solution to not include these pitfalls?

    These can be prevented with simple tests. However, it is not clear that you should prevent the exceptions. In both cases, they are due to the caller violating the input constraints.

    It is also possible that there are other problems, but I haven't spotted them ...

    UPDATE

    When divisor is 10^9, new int[divisor] allocates 4 x 10^9 bytes. That is a lot greater than 1GB. So OutOfMemoryError is a third possibility.