Number of conjugate complex pairs

Question

I need to write a function which fills array rez with the conjugate-complex pairs from the array bounded by p1 and p2. The function returns the number of conjugate-complex pairs placed in the array. Duplicates must not be placed in the sequence. Conjugate-complex pairs are pairs of forms a + bi and a - bi.

This task should be solved using structures and pointer arithmetic. Auxiliary arrays are not allowed.

#include <stdio.h>
typedef struct {
  int im, re;
} complex;
void remove_duplicates(complex *rez, int *number){
    int i,j,k;
    for (i = 0; i < *number; i++) {
    for (j = i + 1; j < *number; j++) {
      if (rez[i].im == rez[j].im && rez[i].re == rez[j].re) {
        for (k = j; k < *number - 1; k++) {
          rez[k].im = rez[k + 1].im;
          rez[k].re = rez[k + 1].re;
        }
        (*number)--;
        j--;
      }
    }
  }
}
int conjugate_complex(complex *p1, complex *p2, complex *rez) {
  int number_of_pairs = 0;
  while (p1 < p2) {
    if (p1->im == p1->re||p1->im == -1*p1->re) {
      number_of_pairs++;
      rez->re = p1->re;
      rez->im = -1*p1->im;
    }
     rez++;
    p1++;
  }
  remove_duplicates(rez,&number_of_pairs);
  return number_of_pairs;
}
int main() {
    int i;
  complex arr1[5] = {{5, 5}, {3, 3}, {-5, -5}, {5, 5}, {-3, 3}};
  complex arr2[5];
  int vel = conjugate_complex(arr1, arr1 + 5, arr2);
  printf("%d\n", vel);
  for (i=0; i<vel; i++)
    printf("(%d,%d) ",arr2[i].im,arr2[i].re);
  return 0;
}

OUTPUT should be:

4
(-5,5) (-3,3) (5,-5) (3,3)

My output is:

5
(-5,5) (-3,3) (5,-5) (-5,5) (3,3)

The problem with my code is that it prints duplicates. Could you help me fix my remove_duplicates function? If I call it in main function it would work. However, I need to call it in the function conjugate_complex.

use `long double` instead of `int` because mathematics have decimals too not just integers — Darth-CodeX, Feb 26 '22 at 20:01
Don't you need the "pairs" to be in the same struct? "-1*p1->im == p1->re" should be (-1*(p1->im)) == p2->im) && (p1->re == p2->re). There are other issues... — Andrew, Feb 26 '22 at 20:03
arr2 (it's empty) is there just to be as border, it enables arr1 to use pointer arithmetic — , Feb 26 '22 at 20:07
The output, only by happenstance, is actually CORRECT (assuming im = b). BTW, better to order code as re then im IMO. — Andrew, Feb 26 '22 at 20:17
arr1 + 5 overflows. What do you mean by "bounded by P2 & p2? Do you want to find pairs among the single values, or just find the pre-defined pairs that are conjugates? Maybe you should re-write this with those answers. — Andrew, Feb 26 '22 at 20:26
I edited code, now I'm really close to correct output, could someone fix my code? — , Feb 26 '22 at 20:59
@Andrew: `arr1+5` does not overflow. `arr1` has five elements, and the C standard defines the behavior of computing the endpoint. — Eric Postpischil, Feb 26 '22 at 21:04
7 mins ago my understnding was/is that arr1={5, 5};arr1+1={3, 3};arr1+2={-5, -5};arr1+3={5, 5};arr1+4={-3, 3};arr1+5 overflows — Andrew, Feb 26 '22 at 21:13
Does anyone know how to delete duplicate pairs? I edited code, I think now works fine, but problem are duplicates — , Feb 26 '22 at 21:36
@Andrew: No, `arr1+1={3, 3}` is not correct. `arr1+1` **points to** the element containing 3 and 3. `arr1[1]` or `*(arr1+1)` would be that element. `arr1+5` points to one beyond the last element. This is defined by C 2018 6.5.6 8. — Eric Postpischil, Feb 26 '22 at 21:50
ok, so "arr1+5 does not overflow", but it "points to one beyond the last element"(isn't that "bad"?) — Andrew, Feb 26 '22 at 21:59
@Andrew: No, it is not bad. The code is using it as the endpoint for a loop, which is precisely why the C standard defines it. `while (p1 < p2)` enters the loop as long as `p1` points to a valid element of the array and stops it when `p1` reaches the endpoint. The parameter `p2` has the value `arr1+5`. — Eric Postpischil, Feb 26 '22 at 22:21
Do you know why my function `remove_duplicates` doesn't work? — , Feb 26 '22 at 22:25
Why don't you use a hash-table, then you wouldn't need to worry about duplicate removal? — Neil, Feb 26 '22 at 22:32
@Neil I don't know what hash-tables are and how to implement them. I googled but I don't see how could I use them in this task... — , Feb 26 '22 at 22:43
Why my function `remove_duplicates` doesn't work in function conjugate_complex, but works in main function? I edited code — , Feb 26 '22 at 22:44
Nb, the answer is 3 not 4; `(-3, 3)` and `(3, 3)` are the same 3+/-3i. — Neil, Feb 27 '22 at 02:23

Neil · Answer 1 · 2022-02-27T20:54:01.323

To see why it would be nice to have some O(n) space, consider what you would do in real life with graph paper. Take each complex number and place a spot in the graph (re, abs(im)). In that way, any duplicates get merged into one. This solution is O(n). (Expected, the hash is O(n) size, so you have to throw out some information, which will lead to collisions.)

It would be better to not duplicate elements in the first place. Whether you are using a Bloom filter to get around the restriction of not having an array, O(n) hash, O(n log n) sort, or an O(n^2) approach (arguably the simplest,) it would be good to have this function, (in pseudo-code, <stdbool.h> is C99, use int, adornments aside):

boolean pair_is_equal(pair a, pair b)

Be aware that a pair is not semantically equivalent to a complex. You can use the same representation (which you've been using, and, considering the output format, the simplest,) but be aware that they represent different things. If you let a complex stand in for a pair:

boolean pair_is_equal(complex a, complex b)

then you have to also also check one of a or b's complex conjugate, (except Im[a] == 0 || Im[b] == 0.) It might also be useful care about 2's-compliment INT_MIN, which is out of the domain of abs and will not have a complement (how to test.)

Number of conjugate complex pairs

1 Answers1