trying to solve 217. Contains Duplicate in C with HashSet.
after i tried to make the calculated index to be always (+) i get an error.
#define BUCKET_SIZE 1000
typedef struct ListNodes {
int val;
struct ListNodes* next;
} ListNode;
typedef struct {
ListNode* buckets[BUCKET_SIZE];
} MyHashSet;
// create hash table
MyHashSet* myHashSetCreate() {
MyHashSet* obj = (MyHashSet*) malloc(sizeof(MyHashSet));
for(int i = 0 ; i < BUCKET_SIZE ; i++ ) {
obj -> buckets[i] = NULL;
}
return obj;
}
bool myHashSet(MyHashSet* obj, int key) {
unsigned int index = key % BUCKET_SIZE; // problem here
ListNode* current = obj->buckets[index];
while(current != NULL) {
if(current -> val == key) return true;
current = current -> next;
}
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = key;
newNode->next = obj->buckets[index];
obj->buckets[index] = newNode;
return false;
}
// task function
bool containsDuplicate(int* nums, int numsSize) {
MyHashSet* obj = myHashSetCreate();
for(int i = 0 ; i < numsSize ; i++) {
if(myHashSet(obj, nums[i])) {
return true;
}
}
return false;
}
unsigned int index = key % BUCKET_SIZE;
result :
Line 23: Char 15: runtime error: load of address 0x6258000078f0 with insufficient space for an object of type 'struct ListNode *' [solution.c] 0x6258000078f0: note: pointer points here
ListNode* current = obj->buckets[index];
i fixed the bug by :
int index = key % BUCKET_SIZE;
or
int index = key % BUCKET_SIZE;
if( index < 0) {
index *= -1;
}
any idea why the code behave weirdly ?
Avoid signed math:
bool myHashSet(MyHashSet* obj, int key) {
unsigned int index = key % BUCKET_SIZE;
change to
bool myHashSet(MyHashSet* obj, unsigned key) {
unsigned int index = key % BUCKET_SIZE;
// or
bool myHashSet(MyHashSet* obj, int key) {
unsigned int index = (unsigned) key % BUCKET_SIZE;
// or
// #define BUCKET_SIZE 1000
#define BUCKET_SIZE 1000u
// or ...
With original unsigned int index = key % BUCKET_SIZE;
, key % BUCKET_SIZE
computes the remainder which is in the -999 to 999 range. Converting a negative number to unsigned
makes for large unsigned
vales.