1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// A simple hash function for integers
6int hash(int value, int size) {
7    return abs(value) % size;
8}
9
10// Set data structure
11typedef struct Set {
12    int *data;
13    int size;
14    int capacity;
15} Set;
16
17Set* createSet(int capacity) {
18    Set *set = (Set*)malloc(sizeof(Set));
19    set->data = (int*)calloc(capacity, sizeof(int));
20    set->size = 0;
21    set->capacity = capacity;
22    return set;
23}
24
25void add(Set *set, int value) {
26    int index = hash(value, set->capacity);
27    while (set->data[index] != 0) {
28        if (set->data[index] == value) return; // already present, do nothing
29        index = (index + 1) % set->capacity;
30    }
31    // Insert new value
32    set->data[index] = value;
33    set->size++;
34}
35
36bool contains(Set *set, int value) {
37    int index = hash(value, set->capacity);
38    while (set->data[index] != 0) {
39        if (set->data[index] == value) return true;
40        index = (index + 1) % set->capacity;
41    }
42    return false;
43}
44
45int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
46    Set *set1 = createSet(1009);  // A prime number close to 1000
47    Set *resultSet = createSet(1009);
48    
49    for (int i = 0; i < nums1Size; i++) {
50        add(set1, nums1[i]);
51    }
52
53    for (int j = 0; j < nums2Size; j++) {
54        if (contains(set1, nums2[j])) {
55            add(resultSet, nums2[j]);
56        }
57    }
58
59    int *result = (int *)malloc(resultSet->size * sizeof(int));
60    int index = 0;
61    for (int i = 0; i < resultSet->capacity; i++) {
62        if (resultSet->data[i] != 0) {
63            result[index++] = resultSet->data[i];
64        }
65    }
66    *returnSize = index;
67
68    return result;
69}
70
71int main() {
72    int nums1[] = {4, 9, 5};
73    int nums2[] = {9, 4, 9, 8, 4};
74    int returnSize;
75    int* result = intersection(nums1, 3, nums2, 5, &returnSize);
76    for (int i = 0; i < returnSize; i++) {
77        printf("%d ", result[i]);
78    }
79    return 0;
80}

1import