CODEWITHSUNDEEP
cmathinteger-arithmetic
Rorschach
Rorschach

Reputation: 764

Overflow happening because of addition?

Hello and sorry for lame title of this post, just couldn't find a better one.

So, I'm solving Codility exercise called NumberOfDiscIntersections. The solution requires some basic sorting and some minor arithmetic operations. I have achieved 93% result, and only one test is failing. The descripton that they provide is following:

For example, for the input [1, 2147483647, 0] the solution returned a wrong answer (got -1 expected 2).

Problem can be seen here.

And here is my solution:

typedef long long int my_type; //can't use unsigned!
#define LIMIT 10000000

//method used by qsort()
int comp(const void* left, const void* right) {
    my_type arg1 = *(const my_type*)left;
    my_type arg2 = *(const my_type*)right;

    if(arg1 < arg2) return -1;
    if(arg2 < arg1) return 1;
    return 0;
}

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)

    //allocate two arrays to hold beginning and ending points of each circle 
    my_type *lower = calloc(N, sizeof(my_type));
    my_type *upper = calloc(N, sizeof(my_type));
    int i;
    my_type count = 0;

    //initialize arrays
    for(i = 0; i < N; i++) {
        lower[i] = i - A[i];
        upper[i] = i + A[i];
    }

    qsort(lower, N, sizeof(my_type), comp);
    qsort(upper, N, sizeof(my_type), comp);

    int open = 0;
    int upper_index = 0;

    for(i = 0; i < N; i++) {
        while(lower[i] > upper[upper_index]) {
            //printf("closing %d\n", upper[upper_index]);
            upper_index++;
            open--;
        }

        open++;
        count += (open-1);

        //printf("opening %d\n", lower[i]);
    }

    free(lower);
    free(upper);

    return ((int)count <= LIMIT) ? (int)count : -1;
}

Upvotes: 0

Views: 68

Answers (1)

Weather Vane
Weather Vane

Reputation: 34583

The right hand side of these

lower[i] = i - A[i];
upper[i] = i + A[i];

performs int addition. You must cast one of the operands:

lower[i] = (my_type)i - A[i];
upper[i] = (my_type)i + A[i];

to prevent integer overflow.

Upvotes: 2

Related Questions