CODEWITHSUNDEEP
c
Bill Tudor
Bill Tudor

Reputation: 97

Find the union of two sets of 10 digit numbers

I'm trying to find the union of two sets of 10 digit numbers, I'm passing along three int arrays: first, second, and comp (this will hold the union set).

So far, I've added first and second into one array. I was thinking about finding the matching indices in comp[] then filter through deleting them. I figure there's a much easier way. Can anyone give me a hint?

Basically I'm taking 

first[] = [1,2,3,4,5,6,7,8,9,10];
second[] = [1,2,3,4,11,12,13,14,15,16];

and I want to return 

comp[] = [5,6,7,8,9,10,11,12,13,14,15,16];

The numbers won't necessarily be in order.

int compound(int first[],int second[],int comp[]){
int i=0;
int indicies[20];
for(int j = 0; j<SIZE; j++){
    comp[i]=first[j];
    i++;
}

for(int k = 0; k<SIZE; k++){
    comp[i]=second[k];
    i++;
}
int z=0;
for(int l = 0; l<SIZE*2; l++){
    for(int m = 0; m<SIZE*2; m++){
        if(comp[l]==comp[m]){
            indicies[z]=m;
            z++;
        }}}


return 0;
}

Upvotes: 1

Views: 172

Answers (3)

ooga
ooga

Reputation: 15511

If the numeric range is small you could do this:

#include <stdio.h>

#define MAX 20  // small numeric range

#define sz(a) (sizeof(a)/sizeof(*(a)))

int xunion(int *a, int sa, int *b, int sb, int *c) {
  int n[MAX] = {0};
  for (int i=0; i<sa; i++) n[a[i]] = 1;
  for (int i=0; i<sb; i++) n[b[i]] = 1;
  int j=0;
  for (int i=0; i<MAX; i++) if (n[i]) c[j++] = i;
  return j;
}

void prn(int *a, int s) {
  while (s-- > 0) printf("%d ", *a++);
  putchar('\n');
}

int main() {
  int a[] = {6, 3, 4, 7, 5};
  int b[] = {2, 4, 5, 7, 6, 3};
  int c[MAX];
  prn(a, sz(a));
  prn(b, sz(b));
  int n = xunion(a, sz(a), b, sz(b), c);
  prn(c, n);
  return 0;
}

Upvotes: 1

Elliott Frisch
Elliott Frisch

Reputation: 201527

I suggest you start by writing a contains(int[], int) method like

#include <stdio.h>
#include <stdbool.h>

bool contains(int arr[], int val) {
  int offset;
  for (offset = 0; arr[offset] != '\0'; offset++) {
    if (arr[offset] == val) return true;
  }
  return false;
}

Then your compound method could be implemented using it with something like

int compound(int first[],int second[],int comp[]){
  int i=0;
  int j;
  for(j = 0; first[j] != '\0'; j++){
    int val = first[j];
    if (contains(second, val) && !contains(comp, val))
      comp[i++] = val;
  }
  return i;
}

Finally, you can test it like

int main(int argc, char *args[]) {
  int a[] = {1,2,3,'\0'};
  int b[] = {2,3,4,'\0'};
  int c[3];
  int count = compound(a,b,c);
  int i;
  for (i = 0; i < count; i++) {
    printf("%i\n", c[i]);
  }
}

Output is

2
3

Upvotes: 3

Deduplicator
Deduplicator

Reputation: 45704

A first good step is (nearly) always sorting.

Sort both input-sets (unless you know they are already sorted).

Then iterate over both at once (two indices) and only add those elements to the output which fulfill your criteria (seems to be union minus intersection, thus only in one).

Bonus: The output-set will be sorted.

Upvotes: 6

Related Questions