Reputation: 3792
I just finished my C solution of Leetcode "Two Sums". But the website says "Runtime Error", without saying which line of code is wrong. The following code runs perfectly in Xcode. Is there anything wrong with my code?
int* twoSum(int* nums, int numsSize, int target);
int main(int argc, const char * argv[]) {
int nums[] = { 1, 2, 4, 8, 16};
int numsSize = 5;
int target = 10;
int *answer = twoSum(nums, numsSize, target);
printf("index1 = %d, index2 = %d\n", answer[0], answer[1]);
return 0;
}
struct bucketLayer {
int data;
int index;
struct bucketLayer* ptr;
};
struct result {
int found;
int index;
};
struct bucketLayer *addData(int data, int index, struct bucketLayer *targetPtr);
struct result findData(int data, int firstIndex, struct bucketLayer *targetPtr);
struct bucketLayer *freeBucket(struct bucketLayer *bucketPtr);
int* twoSum(int* nums, int numsSize, int target) {
struct bucketLayer *buckets[target];
int *answer = (int *)malloc(2 * sizeof(int));
for (int i = 0; i < numsSize; i++) {
buckets[nums[i] % target] = addData(nums[i], i, buckets[nums[i] % target]);
}
for (int i = 0; i < numsSize - 1; i++) {
struct result findResult = findData(target - nums[i], i, buckets[target - nums[i] % target]);
if (findResult.found) {
if (findResult.index > i) {
answer[0] = i+1;
answer[1] = findResult.index + 1;
return answer;
} else {
answer[0] = findResult.index + 1;
answer[1] = i + 1;
return answer;
}
}
}
for (int i = 0; i < target; i++) {
buckets[i] = freeBucket(buckets[i]);
}
return answer;
}
struct bucketLayer *addData(int data, int index, struct bucketLayer *targetPtr) {
if (targetPtr == NULL) {
targetPtr = (struct bucketLayer *)malloc(sizeof(struct bucketLayer));
targetPtr->data = data;
targetPtr->index = index;
targetPtr->ptr = NULL;
} else {
targetPtr->ptr = addData(data, index, targetPtr->ptr);
}
return targetPtr;
}
struct result findData(int data, int firstIndex, struct bucketLayer *targetPtr) {
struct result findResult;
if (targetPtr == NULL) {
findResult.found = 0;
return findResult;
} else {
if (targetPtr->data == data && targetPtr->index != firstIndex) {
findResult.found = 1;
findResult.index = targetPtr->index;
return findResult;
} else {
return findData(data, firstIndex, targetPtr->ptr);
}
}
}
struct bucketLayer *freeBucket(struct bucketLayer *bucketPtr) {
if (bucketPtr != NULL) {
bucketPtr->ptr = freeBucket(bucketPtr->ptr);
free(bucketPtr);
}
return bucketPtr;
}
Upvotes: 0
Views: 2403
Reputation: 84531
After a closer look at the code, the problem is introduced by the use of the variable length array of pointers to struct bucketLayer
. In that instance while there is a static pointer available, the pointer is uninitialized and causes the addData
function to incorrectly handle the pointer. Manual initialization is all that is needed:
struct bucketLayer *buckets[target];
for (int i = 0; i < target; i++)
buckets[i] = NULL;
int *answer = malloc (2 * sizeof *answer);
for (int i = 0; i < numsSize; i++) {
buckets[nums[i] % target] = addData(nums[i], i, buckets[nums[i] % target]);
}
The addData
allocation can also be reduced to:
targetPtr = malloc (sizeof *targetPtr);
Upvotes: 1