Confusion regarding finding the minimum difference between arrays of two element

Question

I came across a post Find the minimum difference between two arrays
and using the concept I tried to solve a problem of SPOJ - http://www.spoj.pl/problems/ACPC11B but strangely I got WA (Wrong Answer) !!!!

I then tried the simple way..
using two for loops..
Calculating the difference between each and every element ...
Then I got AC. !!!!

Can anyone please tell me why this method
if (|A[i+1] - B[j]| < |A[i] - B[j+1]|) then increment i, otherwise increment j fails in this case ????

EDIT: I forgot to mention that when I implemented the first method I have already performed qsort on both the arrays...
Also in the SPOJ question, indexes of the elements whose difference is minimum are not required. Only minimum difference is required !!!

Could be overindexing the array, skipping `A[0]-B[0]`; hard to tell without your actual code — Attila, May 23 '12 at 19:38
@Attila Please have a look at my code and point out my mistake, if any... — Snehasish, May 24 '12 at 08:25

Ted Hopp · Answer 1 · 2012-05-24T05:37:49.700

2

The method in the first link only works if both arrays are sorted. The SPOJ problem involves unsorted arrays. That's why the method did not work. If you sort the arrays, you can apply the first method, but then you'll need to keep track of the original indexes (i.e., the position of each value before sorting). That's doable by converting each value into a (value, index) pair and then sorting the pairs. That way you will have an O(m log m + n log n) solution instead of your brute-force (but correct) O(mn) solution (where m and n are the array lengths).

EDIT Based on your posted code, I have a different answer. Your loop condition is wrong. For instance, if i == (x - 1) but j != (y - 1), the loop will execute and you will be comparing a[x] to b[j]. This is an illegal subscript for a. Also, is this supposed to be reading the same input as described in SPOJ? I don't see where you are reading the number of test cases.

edited May 24 '12 at 05:37

answered May 23 '12 at 19:35

Ted Hopp

232,168
48
399
521

I think you meant O(nlogn + mlogm). n,m being the length of both arrays. – Samy Arous May 23 '12 at 19:55
@TedHopp I forgot to mention that I performed qsort on the arrays before implementing first method... – Snehasish May 24 '12 at 05:03
@Snehasish - If you sorted both arrays, then the method should work. Perhaps you should post your code. – Ted Hopp May 24 '12 at 05:06
@TedHopp Sir, if i == (x - 1), then then the condition i != (x - 1) will become false, and the condition of while loop will thereby be false and it will come out of while loop !!! – Snehasish May 24 '12 at 06:00

score 0 · Answer 2 · answered May 24 '12 at 10:04

You don't compare the very first elements of the arrays. That is, if the minimum difference is |a[0]-b[0]| and that difference does not occur between any other element pairs, you will not find it as your comparison starts with |a[1]-b[0]| and |a[0]-b[1]|.

Samy Arous · Accepted Answer · 2012-05-24T12:27:16.417

Here's what I think should do the trick (based on your code), basically your code didn't check 2 cases:

First when the minimum is between the 2 first values in the arrays.

Second is when we've checked every value in one array but still have values in the second. (Consider the case a[0,1,2], b[-1,-2,-3,-5,-6,2])

#include <stdlib.h>
#include <stdio.h>
#include <time.h>


int comp(const void * a,const void * b)
{
    if (*(int*)a==*(int*)b)
        return 0;
    else if (*(int*)a < *(int*)b)
        return -1;
    else
        return 1;
}

int main()
{
    int x,y;
    printf("x: ");
    scanf ("%d", &x);
    int a[x];
    srand(time(NULL));
    for (int i = 0; i < x; i++)
    {
        a[i] = rand() % 30 - 15;
        //scanf ("%d", &a[i]);
        printf ("%d\n",a[i]);
    }

    printf("y: ");
    scanf ("%d", &y);

    int b[y];
    for (int i = 0; i < y; i++)
    {
        b[i] = rand() % 30 - 15;
        //scanf ("%d", &b[i]);
        printf ("%d\n",b[i]);
    }


    qsort(a,x,sizeof(int),comp) ;
    qsort(b,y,sizeof(int),comp) ;
    int i = 0, j = 0;
    int * inc; // using a pointer to select which var to increment. Avoid repeating code, optional and subjective approach.
    int minimum = abs(a[0]-b[0]); // Set min to be a[0] - b[0] which is never checked in the loop

    /* Added the min > 0 condition to avoid looping unnecessarily and avoid the break statement
    Changed the condition from && to || in order to handle the second case
    Changed the != to < which is more restrictive */
    while (minimum > 0 && (i < (x - 1) || j < (y - 1)))
    {

        int z;
        if ( i == x-1) // we've reached the end of a, inc j automatically
        {
            inc = &j;
            z = abs(a[i]-b[j+1]);
        }
        else if ( j == y -1 ) // we've reached the end of b, inc i automatically
        {
            inc = &i;
            z = abs(a[i+1]-b[j]);
        }
        else // here's the original loop, rewritten to shorten the code
        {
            int zi = abs(a[i+1]-b[j]);
            int zj = abs(a[i]-b[j+1]);
            if ( zi < zj)
            {
                inc = &i;
                z = zi;
            }
            else
            {
                inc = &j;
                z = zj;
            }
        }
        if ( z < minimum)
        {
            minimum = z;
        }

        (*inc)++;
    }
    printf("min: ");
    printf ("%d\n", minimum);
    return 0;

}

Confusion regarding finding the minimum difference between arrays of two element

3 Answers3