NumberOfDiscIntersections overflow in codility test

Question

In the codility test NumberOfDiscIntersections I am getting perf 100% and correctness 87% with the one test failing being

overflow
arithmetic overflow tests
got -1 expected 2

I can't see what is causing that given that I am using long which is 64-bit. And even if I can get it to 100% perf 100% correctness I am wondering if there is a better way to do this that is not as verbose in Java.

edit: figured out a much better way to do with with two arrays rather than a pair class

// you can also use imports, for example:
 import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        int j = 0;
        Pair[] arr = new Pair[A.length * 2];
        for (int i = 0; i < A.length; i++) {
            Pair s = new Pair(i - A[i], true);
            arr[j] = s;
            j++;
            Pair e = new Pair(i + A[i], false);
            arr[j] = e;
            j++;
        }
        Arrays.sort(arr, new Pair(0, true));

        long numIntersect = 0;
        long currentCount = 0;
        for (Pair p: arr) {
            if (p.start) {
                numIntersect += currentCount;
                if (numIntersect > 10000000) {
                    return -1;
                }
                currentCount++;
            } else {
                currentCount--;
            }
        }

        return (int) numIntersect;
    }

    static private class Pair implements Comparator<Pair> {
        private long x;
        private boolean start;
        public Pair(long x, boolean start) {
            this.x = x;
            this.start = start;
        }

        public int compare(Pair p1, Pair p2) {
            if (p1.x < p2.x) {
                return -1;
            } else if (p1.x > p2.x) {
                return 1;
            } else {
                if (p1.start && p2.start == false) {
                    return -1;
                } else if (p1.start == false && p2.start) {
                    return 1;
                } else {
                    return 0;
                }
            }
        }
    }
}

Answer 1

Look at this line:

Pair s = new Pair(i + A[i], true);

This is equivalent with Pair s = new Pair((long)(i + A[i]) , true);

As i is integer, and A[i] is also integer, so this can cause overflow, as value in A[i] can go up to Integer.MAX_VALUE, and the cast to long happened after add operation is completed.

To fix:

Pair s = new Pair((long)i + (long)A[i], true);

Note: I have submitted with my fixed and got 100%

https://codility.com/demo/results/demoRRBY3Q-UXH/

Answer 2

My todays solution. O(N) time complexity. Simple assumption that number of availble pairs in next point of the table is difference between total open circle to that moment (circle) and circles that have been processed before. Maybe it's to simple :)

  public int solution04(int[] A) { 
    final int N = A.length;
    final int M = N + 2;
    int[] left  = new int[M]; // values of nb of "left"  edges of the circles in that point
    int[] sleft = new int[M]; // prefix sum of left[]
    int il, ir;               // index of the "left" and of the "right" edge of the circle

    for (int i = 0; i < N; i++) { // counting left edges
      il = tl(i, A);
      left[il]++;
    }

    sleft[0] = left[0];
    for (int i = 1; i < M; i++) {// counting prefix sums for future use
      sleft[i]=sleft[i-1]+left[i];
    }
    int o, pairs, total_p = 0, total_used=0;
    for (int i = 0; i < N; i++) { // counting pairs
      ir = tr(i, A, M);
      o  = sleft[ir];                // nb of open till right edge
      pairs  = o -1 - total_used;
      total_used++;
      total_p += pairs;
    }
    if(total_p > 10000000){
      total_p = -1;
    }
    return total_p;
  }

  int tl(int i, int[] A){
    int tl = i - A[i]; // index of "begin" of the circle
      if (tl < 0) {
        tl = 0;
      } else {
        tl = i - A[i] + 1;
      }
    return tl;
  }
  int tr(int i, int[] A, int M){
    int tr;           // index of "end" of the circle
      if (Integer.MAX_VALUE - i < A[i] || i + A[i] >= M - 1) {
        tr = M - 1;
      } else {
        tr = i + A[i] + 1;
      }
      return tr;
  }