Counting pairs of numbers that differ by a given amount

Question

I am trying to do these online competitions where you get the given exercise and are supposed to upload the source file. The site is not in English so I will try to summarize the exercise.

The first line of input states P, the number of problems ( 1 <= P <= 100 ). Subsequently, there are two lines for each problem. The first contains numbers X and Y ( 1 <= X, Y <= 100000) — X being number of elements and Y being the difference I am looking for. On the next line there are X numbers (0 <= N <= 100000) divided by a space. For every problem, I am supposed to print the number of pairs that differ by Y.

As an example input :

2
5 2
1 5 3 4 2
5 4
6 3 6 2 2

Example output:

3
4

I wrote a simple programme that did the thing but when I uploaded the source file I got "time limit exceeded" error. After that I discovered that my program is unable to handle big input. I tried to move on to the next exercise but I discovered almost all of them have big inputs. I tried to improve it myself, then I tried to google it, but sadly I still cannot get past the error. This is the code I ended up with :

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

#define SIZE 80000

int compare(const void *a, const void *b);

int main(int argc, char const *argv[]) {
  char buffer[SIZE];
  unsigned int numberOfGames, numberOfStudents, wantedDifference;
  unsigned int numberOfDifferentPairs;
  unsigned int counter;
  size_t i, j;

  scanf("%u", &numberOfGames);

  while (numberOfGames--) {
    scanf("%u %u", &numberOfStudents, &wantedDifference);
    scanf("\n");
    unsigned long long int *studentsHeights =
        (unsigned long long int *)malloc(sizeof(unsigned long long int) * numberOfStudents);
    counter = 0;
    numberOfDifferentPairs = 0;
    studentsHeights[counter] = 0;
    while (counter < numberOfStudents) {
      fgets(buffer, SIZE, stdin);
      size_t stringSize = strlen(buffer);
      for (i = 0; i < stringSize; i++) {
        if (buffer[i] == ' ' || buffer[i] == EOF || buffer[i] == '\n') {
          counter++;
          if (counter < numberOfStudents)
            studentsHeights[counter] = 0;
        } else {
          studentsHeights[counter] =
              studentsHeights[counter] * 10 + (buffer[i] - '0');
        }
      }
    }
    qsort(studentsHeights, numberOfStudents, sizeof(unsigned int), compare);
    for (i = 0; i < numberOfStudents - 1; i++) {
      unsigned int lastAddition;
      if (studentsHeights[i] == studentsHeights[i - 1]) {
        numberOfDifferentPairs += lastAddition;
        continue;
      } else {
        lastAddition = 0;
      }
      for (j = i + 1; j < numberOfStudents; j++) {
        if ((studentsHeights[j] - studentsHeights[i]) == wantedDifference) {
          numberOfDifferentPairs++;
          lastAddition++;
        }
      }
    }
    printf("%u\n", numberOfDifferentPairs);
  }
  return 0;
}

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

I know I am probably doing some trivial mistake but if you could point it out for me I would be really grateful.

There are the variables I used:

• P = numberOfGames
• X = numberOfStudents
• Y = wantedDifference
• N = studentsHeights

Answer 1

Bug

When I ran your program, it didn't work. It turns out you have a problem here:

qsort(studentsHeights, numberOfStudents, sizeof(unsigned int), compare);

The type of the studentsHeights array is unsigned long long, but you are sorting as if it were an array of unsigned int. This causes the sort to not work properly.

Input parsing too complicated

You have a custom integer parser that is totally unnecessary. Perhaps you thought it would make your program faster, but input parsing isn't what is making your program too slow.

Solution is accurate but too slow

Your solution works but it takes \$O(n^2)\$ time because of your nested loop. One easy way to make your program \$O(n \log n)\$ would be to change your j loop to binary search for the start of the desired height and then count the number of duplicates of that height. This would most likely make your program run within the time limit. But there is actually a faster and simpler way as well.

\$O(n)\$ solution possible

Instead of sorting and counting duplicates like you are doing now, you can take advantage of the fact that the input is limited to numbers in the range 0..100000. You can set up an array to hold the count of each number and then iterate across the array of counts. Here is how you would do it:

#include <stdio.h>
#include <string.h>

#define MAX_HEIGHT        100000

unsigned long heightCounts[MAX_HEIGHT + 1];

int main(void)
{
    int numTestcases = 0;

    scanf("%d", &numTestcases);
    while (numTestcases--) {
        unsigned long numHeights = 0;
        unsigned long difference = 0;
        unsigned long i          = 0;
        unsigned long total      = 0;

        scanf("%lu %lu", &numHeights, &difference);
        memset(heightCounts, 0, sizeof(heightCounts));
        for (i = 0; i < numHeights; i++) {
            unsigned long height;
            scanf("%lu", &height);
            heightCounts[height]++;
        }

        for (i = 0; i <= MAX_HEIGHT - difference; i++)
            total += heightCounts[i] * heightCounts[i+difference];

        printf("%lu\n", total);
    }
}

Note: I use unsigned long because int is only guaranteed to be 16 bits. The problem requires values that are 32 bits long. The maximum answer given the problem constraints is 2500000000 which fits in a 32 bit unsigned value.

Answer 2

Your solution is \$O(X^2)\$ which is too slow for \$X\approx 10^5\$.

Instead of checking differences with two nested loops, you should just loop over the first element a and perform binary search to find the number of elements of the form a+Y. This will reduce the complexity to \$O(X \log X)\$ which will be fast enough.

Answer 3

Since you sort the list, you don't have to check every height against every other. Use the structure of your data to skip unnecessary checks. In your code, the indices i and j run through the list multiple times to find the differences. But, since the list is sorted, there comes a point where j reaches numbers with too great a difference with the number at i, so you can stop and go to the next i.

To be more clear, you can do a single run through the list with two indices, one for the shorter student, one for the taller. If the difference in height between the indices is greater than the wanted height, increment the shorter index. If the difference is less, increment the taller index. If the difference is equal to the desired amount, count it and increment the shorter.

int shortIndex = 0;
int tallIndex = 0;

while(tallIndex < numberOfStudents)
{
    int difference = studentsHeights[tallIndex] - studentsHeights[shortIndex];

    if(difference > wantedDifference)
    {
        shortIndex++;
    }
    else if(difference < wantedDifference)
    {
        tallIndex++;
    }
    else
    {
        numberOfDifferentPairs++;
        shortIndex++;
    }
}

Other comment:

I don't understand what the variable lastAddition is doing in your code.

Answer 4

while (counter < numberOfStudents) {
  fgets(buffer, SIZE, stdin);
  size_t stringSize = strlen(buffer);
  for (i = 0; i < stringSize; i++) {
    if (buffer[i] == ' ' || buffer[i] == EOF || buffer[i] == '\n') {
      counter++;
      if (counter < numberOfStudents)
        studentsHeights[counter] = 0;
    } else {
      studentsHeights[counter] =
          studentsHeights[counter] * 10 + (buffer[i] - '0');
    }
  }
}

This seems awfully complex. The code uses scanf elsewhere: why not here?

---

One way to restructure and simplify would be to observe that since a number pairs with numbers either Y below or Y above them, you potentially have chains of linked numbers and those chains can be separated because the elements in a chain have the same value % Y. This suggests using a radix-based comparison (unfortunately with a global variable)

int compareRadixY(const void *a, const void *b) {
  unsigned int aval = *(unsigned int *)a;
  unsigned int bval = *(unsigned int *)b

  unsigned int arem = aval % Y;
  unsigned int brem = bval % Y;
  if (arem < brem) return -1;
  if (arem > brem) return 1;

  unsigned int adiv = aval / Y;
  unsigned int bdiv = bval / Y;
  if (adiv < bdiv) return -1;
  if (adiv > bdiv) return 1;

  return 0;
}

After qsort the scan is much simpler: you only have to compare each element to the ones immediately after it. (It would be "the one immediately after it", but you have to take into account repeated values).