Xvolve programming assignment

You are given two lines.
the first line tells you how many numbers (N) are in the array, the second tells you the difference(K) that you must find.
The second line give you a string of numbers.
Your goal is to count the number of numbers that have a difference (K).

input
5 2
1 5 3 4 2

output
3

in the above input N is 5 and K is 2.  I must find all numbers that have a difference of 2.
There are two ways to do this.  The brute fore way and the better way.  The brute force way does it the way that you would expect.  Create an array of numbers and for each number compare it to every other number until you get to the end.  then you increment to the next number lined up and compare that to every other number until you reach the end.  The running time of this algorithm is O(n^2).  It gets the job done but it does too many comparisons.

the brute force method is called match1.
The better method is called match2.

First it sorts the array of numbers.  We start at the left most index i and compare it to index j.  We will compare it until the values of j are greater than the expected diff.  If it is less than K we increment j to the next.  if it is the same as K then we increment numberOfMatches and then increment J.

This actuall results in much less comparisons.

look at my test cases:

$ 

(10)

3

(9)

3

$ 

(31996000)

0

(7999)

0

$

(7998000)

0

(3999)

0

$ 

(45)

0

(9)

0

After the dollar sign we the I show the number of comparisons, the number of matchs for brute force, the next two are the better method.  Observe the difference.

I think the better method is O(nlogn)

Code is below

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

int compare(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}

int match1(int *arrOfNum, int len, int diff) {
int i,j;
int numMatches=0;
int numComparisons = 0;
    for(i = 0; i < len-1; ++i) {
    for(j = i + 1; j < len; ++j) {
    //printf("%d - %d\n", arrOfNum[i], arrOfNum[j]);
    numComparisons++;
    if(abs(arrOfNum[i] - arrOfNum[j]) == diff) {
    numMatches++;
    }
    }
    }
    printf("(%d)\n", numComparisons);
    return numMatches;
}

int match2(int *arrOfNum, int len, int diff) {
qsort(arrOfNum, len, sizeof(int), compare);
    int i = 0, j = i + 1;
    int *a = arrOfNum;
    int numMatches = 0;
    int numComparisons = 0;
    for(; i < len-1;++i) {
    for(j = i + 1; j < len;++j) {
    //printf("%d - %d\n", arrOfNum[i], arrOfNum[j]);
    numComparisons++;
    if(a[i] + diff > a[j]) {continue;}
    else if(a[i] + diff == a[j]){
    numMatches++;
    } else {
    break;
    }
    }
    }
    printf("(%d)\n", numComparisons);
    return numMatches;
}



int main(int argc, char **argv) {
    char cN[10];
    char cK[10];
    char number[20];
    FILE *f = fopen(argv[1], "r");
    if (!f){ //error
        return -1;
    }
    fscanf(f, "%s %s", cN, cK);
    int N = (int)strtol(cN, NULL, 10);
    int K = (int)strtol(cK, NULL, 10);

    int numMatches = 0;
    int arrOfNum[100000];
    int i = 0;
    while(1 == fscanf(f, "%s", number)) {
    arrOfNum[i] = (int)strtol(number, NULL, 10);
    ++i;
    }


    numMatches = match1(arrOfNum, N, K);
    printf("%d\n", numMatches);
     numMatches = match2(arrOfNum, N, K);

    printf("%d\n", numMatches);
    return 0;
}