13 Replies - 1651 Views - Last Post: 19 May 2019 - 05:44 PM Rate Topic: -----

#1 nexaen   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 18-May 19

Find elements with a given difference in an array

Posted 18 May 2019 - 10:50 AM

1. Summary
1.1. Language: C

I have an array like this {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:

Given array:
{30, 219, 220, 221, 216, 220};

Difference k = 9;

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

Although, array could be like this: {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:

#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]]);
              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 52 & 57-value q in ::
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 51-number 6 in ::
arr[6]  //this value is not logical, I just made it based on a simple guess



line 28 variable m in ::
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 11 array size in ::
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:
https://repl.it/repls/SuburbanRelevantDisassembly





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


Thanks in advance

Is This A Good Question/Topic? 0
  • +

Replies To: Find elements with a given difference in an array

#2 jimblumberg   User is online

  • member icon

Reputation: 5761
  • View blog
  • Posts: 17,640
  • Joined: 25-December 09

Re: Find elements with a given difference in an array

Posted 18 May 2019 - 12:44 PM

You really really need to start using meaningful variable names. For example:

int AveElements(int a[], int n, int k)

What is the purpose of these variables?

Next:
int main()
{
    int a[] = {30, 219, 220, 221, 216, 220};
    int k = 9;

Again a worthless name along with a meaningless "magic number". What is the purpose of that magic number?

Next:
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];

Be careful you are using a VLA for that last array. VLA (Variable Length Arrays) are only truly supported in C99 programs. You really should stick with "regular" arrays that use compile time constants for the sizes.

Quote

Note 1. size of array is not fixed. Number of elements could be 3 or 5 or 8 or more.

Then you probably should be using malloc to allocate the memory for your arrays after you have determined the proper size.

Lastly, for now, your function is doing too much, IMO, you really should consider more smaller functions.


Jim
Was This Post Helpful? 0
  • +
  • -

#3 jimblumberg   User is online

  • member icon

Reputation: 5761
  • View blog
  • Posts: 17,640
  • Joined: 25-December 09

Re: Find elements with a given difference in an array

Posted 18 May 2019 - 01:30 PM

Also posted here.
Was This Post Helpful? 2
  • +
  • -

#4 german-one   User is offline

  • D.I.C Head
  • member icon

Reputation: 23
  • View blog
  • Posts: 60
  • Joined: 05-August 18

Re: Find elements with a given difference in an array

Posted 18 May 2019 - 02:35 PM

I guess something like that may work
#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;
}


Was This Post Helpful? 1
  • +
  • -

#5 nexaen   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 18-May 19

Re: Find elements with a given difference in an array

Posted 18 May 2019 - 03:29 PM

View Postgerman-one, on 18 May 2019 - 02:35 PM, said:

I guess something like that may work

:^: :^: :^:
Works like a charm. I appreciate your help.
I can learn a lot from your work.
Thank you :^: :smile2:
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,995
  • Joined: 05-May 12

Re: Find elements with a given difference in an array

Posted 18 May 2019 - 04:03 PM

german-one: Please don't spoonfeed answers to posters. We want people to do their own work so that they have a better chance of learning as they go through the discovery process.
Was This Post Helpful? 2
  • +
  • -

#7 german-one   User is offline

  • D.I.C Head
  • member icon

Reputation: 23
  • View blog
  • Posts: 60
  • Joined: 05-August 18

Re: Find elements with a given difference in an array

Posted 18 May 2019 - 04:22 PM

I just hope that anything that was not yet clear enough will be asked. But I fully agree that nobody learns from copy/paste.
Was This Post Helpful? 1
  • +
  • -

#8 nexaen   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 18-May 19

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 08:57 AM

@ #6 Skydiver, it depend on you viewpoint. I see it as helping and teaching/learning. Not everyone learns the way you learnt. To me, that solutions has a lot to learn. I will learn "assert" and the way he structured the code.
Was This Post Helpful? 0
  • +
  • -

#9 german-one   User is offline

  • D.I.C Head
  • member icon

Reputation: 23
  • View blog
  • Posts: 60
  • Joined: 05-August 18

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 09:50 AM

I upvoted Skydiver's reply because he has a lot of forum experiences. Unfortunately many questioners here and elsewhere are just looking for someone who writes the code or who makes their homework. In this case posting solutions is entirely counterproductive. On the other hand posting some pieces of code every now and then has some advantages
1) People get a reference of how the code could look like if it was written by an experienced person.
2) People who analyze the code might learn something new. And, as I already pointed out, I expect questions and am willing to answer until all uncertainties are cleared up.
3) Websites where people find solutions will get a higher ranking and get more visitors, which helps to keep the site alive.
4) Last but not least - If I offer code then I also expect that people criticize things that I could have made better. I'm still keen on learning and to improve my skills.

But that's all rather off-topic in this thread. Apparently the way that the volunteers here are teaching programming has been proven to work. So, I'll accept it.
Was This Post Helpful? 1
  • +
  • -

#10 nexaen   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 18-May 19

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 04:06 PM

german-one, Could you please explain about followings?

1. I couldn't find any reference for Diff(). What is difference between abs() and Diff()? Could you please give me a source to read about it?
2. Can you please explain why did you use const int *const array and *const p_count and size_t?
3. Those pointers(*) and addresses (&) are confusing for me. For example in int sum = ConditionalSum(array, length, max_diff, &count); in main(); why did you use address of count (&count)? Is it possible to call the variable directly and not the address?
4. In line 53, why did you use pointer for p_count to *p_count = count; ? Is it why you called address of count in previous question? Can we call them directly?
Was This Post Helpful? 0
  • +
  • -

#11 nexaen   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 18-May 19

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 04:45 PM

It's bad that there is no edit option available for me.
Regarding Question.1, it is my bad. That Diff() is a function in line 13.
I'm trying to rewrite the whole code in a simple way. using abs() instead of that diff(), using regular printf instead of PRINTF(), and some other small changes.
Was This Post Helpful? 0
  • +
  • -

#12 jimblumberg   User is online

  • member icon

Reputation: 5761
  • View blog
  • Posts: 17,640
  • Joined: 25-December 09

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 05:05 PM

Quote

2. Can you please explain why did you use const int *const array and *const p_count and size_t?

What exactly has you confused? Is it the use of the const keyword? Or the use of the pointers themselves?

Quote

in main(); why did you use address of count (&count)?

Do you know the difference between pass by value and pass by "reference"? When passing by value any changes made in the function are lost when the function returns. If you want to use the value computed in the function after the function you need to pass by "reference".

Quote

In line 53, why did you use pointer for p_count to *p_count = count; ? Is it why you called address of count in previous question? Can we call them directly?

No, you want to change the value held in that variable, not the address so you need to dereference that pointer (^pointer = ??).

Quote

I'm trying to rewrite the whole code in a simple way.

This is a good idea. You should just use the "given" code as a sort of reference and write the whole program yourself. But do note the use of more descriptive variable names and function.

By the way, IMO, the ConditionalSum() function is trying to do too much, consider breaking that function into smaller pieces, try to get each piece to do one thing, and do that one thing well. Having small functions that can be tested independently will make your program more robust and give you functions that will be easier to reuse on your next projects.

Jim
Was This Post Helpful? 0
  • +
  • -

#13 german-one   User is offline

  • D.I.C Head
  • member icon

Reputation: 23
  • View blog
  • Posts: 60
  • Joined: 05-August 18

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 05:08 PM

View Postnexaen, on 19 May 2019 - 04:06 PM, said:

1. I couldn't find any reference for Diff(). What is difference between abs() and Diff()? Could you please give me a source to read about it?

Diff() is a custom function. I implemented it, so you won't find any other reference than in my code. I just didn't include math.h, but of course you can use abs(array[idx - 1] - array[idx]) for the same purpose.

View Postnexaen, on 19 May 2019 - 04:06 PM, said:

2. Can you please explain why did you use const int *const array and *const p_count and size_t?

As to const:
I recommend to read declarations from right to left. E.g. array is a constant pointer to an int which is constant. Constant pointer means that you must not change the passed address. Constant value means that you must not change the content of the memory that the pointer variable points to. Having declarations like that in the parameter list protects you from accidential changes in the function of things that you don't want to change. In those cases the compiler will complain. The compiled program will most likely the same with or without const. So, take it as an insurance for the developer.
size_t is an unsigned integral type. I'ts widely used to represent sizes, lengths and counts. Numbers that are never negative by their purpose.

View Postnexaen, on 19 May 2019 - 04:06 PM, said:

3. Those pointers(*) and addresses (&) are confusing for me. For example in int sum = ConditionalSum(array, length, max_diff, &count); in main(); why did you use address of count (&count)? Is it possible to call the variable directly and not the address?

Function parameters get a copy of the passed argument. If you pass the value of count, then you can change the copied value in the function, but the value in main() is not affected and keeps being the same as before. The address-of operator (&) determines the address of the variable in main(). The function receives a copy of this address. By its dereferencing using * in the function you access the memory of the original variable in main(). Thus, the value of variable count in main() will be changed from within the function. The reason why I used this technique is that a function can't return more than one value. Since you need both the sum and the number of elements matched to caculate the average, it's a common possibility to achive that.

View Postnexaen, on 19 May 2019 - 04:06 PM, said:

4. In line 53, why did you use pointer for p_count to *p_count = count; ? Is it why you called address of count in previous question? Can we call them directly?

I think I already explained that. If you change a copy of a value, you don't change the original value. Unlike in declaration (where the asterisk operator marks a pointer variable as such) in this case the * operator dereferences the pointer to get access to the memory range it points to.
Was This Post Helpful? 0
  • +
  • -

#14 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,995
  • Joined: 05-May 12

Re: Find elements with a given difference in an array

Posted 19 May 2019 - 05:44 PM

Perhaps I'm missing something about the problem. Why is the code in post #4 only comparing adjacent array elements, while the original code in post #1 comparing all elements. My understanding is that problem is asking that all elements be compared.

In other words, my understanding is that given these two arrays, and k == 9, they both should give the same results:
{30, 219, 220, 221, 216, 220}
{30, 219, 20, 220, 10, 221, 40, 216, 50, 220}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1