Two Sum Problem Classic Hash Solution in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum Classic Hash Solution

What is the output of the following C code that solves the Two Sum problem using a hash map approach?

DSA C

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* hash = (int*)calloc(2048, sizeof(int));
    int* result = (int*)malloc(2 * sizeof(int));
    for (int i = 0; i < 2048; i++) hash[i] = -1;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int hashIndex = complement & 2047;
        if (hash[hashIndex] != -1 && nums[hash[hashIndex]] == complement) {
            result[0] = hash[hashIndex];
            result[1] = i;
            *returnSize = 2;
            free(hash);
            return result;
        }
        hash[nums[i] & 2047] = i;
    }
    *returnSize = 0;
    free(hash);
    free(result);
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize = 0;
    int* indices = twoSum(nums, 4, target, &returnSize);
    if (indices != NULL) {
        printf("%d -> %d -> null\n", nums[indices[0]], nums[indices[1]]);
        free(indices);
    } else {
        printf("No solution found\n");
    }
    return 0;
}

A 11 -> 15 -> null

B 7 -> 2 -> null

C 2 -> 7 -> null

D No solution found

💡 Hint

Think about which two numbers add up to the target 9 in the array.

The code finds indices of two numbers that add up to the target 9. The pair is 2 and 7, so the output prints their values in order found: 2 -> 7 -> null.

🧠 Conceptual

intermediate

Understanding Hash Map Usage in Two Sum

In the classic hash solution for Two Sum, why do we use a hash map to store indices of numbers?

A To sort the array before searching for pairs

B To reverse the array for easier traversal

C To store the sum of all pairs for later use

D To quickly check if the complement of the current number exists in the array

💡 Hint

Think about how to find pairs that add up to the target efficiently.

The hash map stores indices of numbers to quickly find if the complement (target - current number) exists, enabling O(n) time complexity.

🔧 Debug

advanced

Identify the Error in Hash Index Calculation

What error will occur in this hash index calculation line in the Two Sum hash solution? int hashIndex = complement & 2047;

A It correctly calculates the hash index without error

B It may cause incorrect indexing if complement is negative

C It causes a syntax error due to missing parentheses

D It causes a runtime division by zero error

💡 Hint

Consider what happens if complement is negative when using bitwise AND.

If complement is negative, bitwise AND with 2047 may produce an invalid index, causing incorrect behavior or out-of-bounds access.

🚀 Application

advanced

Result of Two Sum with No Valid Pair

What will the output be when running the Two Sum classic hash solution on the array [1, 2, 3, 4] with target 8?

DSA C

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* hash = (int*)calloc(2048, sizeof(int));
    int* result = (int*)malloc(2 * sizeof(int));
    for (int i = 0; i < 2048; i++) hash[i] = -1;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int hashIndex = complement & 2047;
        if (hash[hashIndex] != -1 && nums[hash[hashIndex]] == complement) {
            result[0] = hash[hashIndex];
            result[1] = i;
            *returnSize = 2;
            free(hash);
            return result;
        }
        hash[nums[i] & 2047] = i;
    }
    *returnSize = 0;
    free(hash);
    free(result);
    return NULL;
}

int main() {
    int nums[] = {1, 2, 3, 4};
    int target = 8;
    int returnSize = 0;
    int* indices = twoSum(nums, 4, target, &returnSize);
    if (indices != NULL) {
        printf("%d -> %d -> null\n", nums[indices[0]], nums[indices[1]]);
        free(indices);
    } else {
        printf("No solution found\n");
    }
    return 0;
}

A No solution found

B 1 -> 7 -> null

C 3 -> 5 -> null

D 4 -> 4 -> null

💡 Hint

Check if any two numbers in the array add up to 8.

No two numbers in [1,2,3,4] add up to 8, so the function returns NULL and prints 'No solution found'.

❓ Predict Output

expert

Output of Two Sum with Duplicate Numbers

What is the output of this Two Sum classic hash solution when the input array contains duplicates?

DSA C

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* hash = (int*)calloc(2048, sizeof(int));
    int* result = (int*)malloc(2 * sizeof(int));
    for (int i = 0; i < 2048; i++) hash[i] = -1;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int hashIndex = complement & 2047;
        if (hash[hashIndex] != -1 && nums[hash[hashIndex]] == complement) {
            result[0] = hash[hashIndex];
            result[1] = i;
            *returnSize = 2;
            free(hash);
            return result;
        }
        hash[nums[i] & 2047] = i;
    }
    *returnSize = 0;
    free(hash);
    free(result);
    return NULL;
}

int main() {
    int nums[] = {3, 3, 4, 5};
    int target = 6;
    int returnSize = 0;
    int* indices = twoSum(nums, 4, target, &returnSize);
    if (indices != NULL) {
        printf("%d -> %d -> null\n", nums[indices[0]], nums[indices[1]]);
        free(indices);
    } else {
        printf("No solution found\n");
    }
    return 0;
}

A 3 -> 3 -> null

B 4 -> 2 -> null

C 5 -> 1 -> null

D No solution found

💡 Hint

Look for two numbers that add up to 6, including duplicates.

The two 3's at indices 0 and 1 add up to 6, so output is '3 -> 3 -> null'.