Thread: Find elements with a given difference in an array

1. Summary
1.1. Language: C


I have an array like this

Code:

{30, 220, 219, 220, 221}

, and I have a difference value k.
I want to get all elements of the array which differences between them is less than that difference (k). Then return the average of those valid values.


Note 1. size of array is not fixed. Number of elements could be 3 or 5 or 8 or more.
Note 2. duplicate elements should not be removed. Else, it could affect averaging section.




1.2. Example:

Code:

Given array: {30, 219, 220, 221, 216, 220};
Difference k = 9;

I am looking for elements 219,220,221,216,220. Then return average of them in integer, which is 219.


Although, array could be like this:

Code:

{220, 219, 220, 30, 216, 224, 217} //larger array size
or {222, 220, 219, 220, 221} // all elements are within the difference range
or {30, 66, 89, 220, 221} // more elements are out of range

2. Background


I wrote the following code.
At first, I am finding indexes of eligible elements. Then removing duplicate of indexes (not elements), then averaging.




3. The code:

Code:

#include <stdio.h> 
#include <math.h>




int AveElements(int a[], int n, int k)
{
  printf( "n is %d \tand\t", n); //debug
  printf( "k is %d\n\n", k); //debug
//////////////////////////////////////// finding indexes ////////////////
//credit: https://www.geeksforgeeks.org/pairs-difference-less-k/
  int index[n*2];
  int res = 0;
  for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
          if (abs(a[j] - a[i]) < k) {
              index[res] = j;
              printf("index[%d]= %d,\t", res, index[res]); //debug
              res++;
              index[res] = j;
              //printf("(%d,%d), (%d,%d)\n", i, j, a[i], a[j]); //debug
              printf("index[%d]= %d,\n", res, index[res]);
              res++;
          }
       }
    }
///////////////////////////////////////// removing duplicate indexes //////
// credit: https://www.studytonight.com/c/programs/array/remove-duplicate-element-program
  int i, j, t, m=n*2;
  for (i = 0; i < m; i++)
  {
      for (j = i + 1; j < m; )
      {
          if (index[j] == index[i])
          {
              printf("aj[%d]=%d,\tai[%d]=%d\n", j,a[index[j]],i,a[index[i]]); //debug
              for (t = j; t < m; t++)
              {
                  index[t] = index[t + 1];
              }
              m--;
          }
          else
          {
              j++;
          }
       }
    }




//////////////////////////////////////////////averaging ///////////
  int arr[6],avg=0,q=i;
  for (int i = 0; i <q; i++ ) {
      arr[i]=a[index[i]];
      avg+=arr[i];
      printf( "a[%d] : %d\n", i, arr[i]); //debug
  }    
  avg/=q;
  printf( "Average : %d\n", avg); //debug
////////////////////////////////////////////////////////////////
    return avg;
}






int main()
{
    int a[] = {30, 219, 220, 221, 216, 220};
    int k = 9;
    int n = sizeof(a) / sizeof(a[0]);
  /////////////////////////////////
    printf("\nGiven array: {");
    for (int i = 0; i <n; i++ ) {
      printf("%d", a[i]);
      if(i<n-1){
        printf(", ");
      }
    }
    printf("}\n\n");
  /////////////////////////////////
  AveElements(a, n, k);
   ///////////////////////////////




    return 0;
}

4. Issues


There are issues with array sizes and loop numbers in this code:
I cannot make the code generic and flexible in array sizes or loop numbers.
For example if you look at:
line 56 & 61-value q in ::

Code:

for (int i = 0; i <q; i++ ) and avg/=q;. Currently it is set to variable i, but it doesn't always work with different array sizes and different number of eligible elements.

line 55-number 6 in ::

Code:

arr[6]  //this value is not logical, I just made it based on a simple guess

line 30 variable m in ::

Code:

m=n*2;  //this value is not logical, I just made it based on a simple guess. It will be problematic with changing either number of elements or number of eligible elements.

line 13 array size in ::

Code:

index[n*2]; //this array size is not logical, I just made it based on a simple guess. It will be problematic with changing either number of elements or number of eligible elements.

A copy of my code, with line numbering, could be found at:

Code:

https://repl.it/repls/SuburbanRelevantDisassembly

Looking forward to have your help/suggestions, or completely a better solution compared to this code.




Thanks in advance

Have you considered sorting the array first? It should be easier to find runs of numbers within the difference that way.

That code compares adjacent elements for the difference. I haven't tested, but I believe this means it only works correctly with a sorted array.