Thread: Find elements with a given difference in an array

  1. #1
    Registered User
    Join Date
    May 2019
    Posts
    2

    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
    Last edited by nexaen; 05-18-2019 at 12:22 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,851
    Have you considered sorting the array first? It should be easier to find runs of numbers within the difference that way.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2019
    Posts
    2
    No. But I found a solution from another person, as below:

    Posting here as a record, if someone else is in need.
    Code:
    #include<stdio.h>
    //#define NDEBUG
    #include<assert.h>
    
    #ifdef NDEBUG
    # define PRINTF(...)
    #else
    # define PRINTF(...) printf(__VA_ARGS__)
    #endif
    
    
    int Diff(const int num1, const int num2)
    {
      if (num1 > num2)
        return num1 - num2;
    
      return num2 - num1;
    }
    
    
    int ConditionalSum(const int *const array, const size_t array_length, const int max_diff, size_t *const p_count)
    {
      assert(array != NULL);
      int found = 0,
          sum = 0;
      size_t count = 0;
    
      for (size_t idx = 1; idx < array_length; ++idx)
      {
        if (Diff(array[idx - 1], array[idx]) <= max_diff)
        {
          if (found == 0)
          {
            PRINTF("%d ", array[idx - 1]);
            sum += array[idx - 1];
            ++count;
          }
    
          PRINTF("%d ", array[idx]);
          sum += array[idx];
          ++count;
          found = 1;
        }
        else
          found = 0;
      }
    
      if (count != 0)
        PRINTF("\n");
    
      if (p_count != NULL)
        *p_count = count;
    
      return sum;
    }
    
    
    int Average(const int sum, const size_t count)
    {
      assert(count != 0);
      return sum / count;
    }
    
    
    int main(void)
    {
      const int array[] = { 22, 220, 219, 220, 30, 0, 216, 224, 217, 12 },
                max_diff = 8;
      size_t count = 0,
             length = sizeof(array) / sizeof(*array);
      int sum = ConditionalSum(array, length, max_diff, &count);
    
      if (count == 0)
        puts("no values matched");
      else
        printf("average: %d\n", Average(sum, count));
    
      return 0;
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,851
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 12-21-2012, 11:48 PM
  2. Replies: 13
    Last Post: 01-18-2012, 08:09 PM
  3. Replies: 5
    Last Post: 10-17-2010, 01:30 PM
  4. Replies: 5
    Last Post: 12-05-2007, 04:39 PM
  5. Replies: 2
    Last Post: 08-03-2003, 10:01 AM

Tags for this Thread