Two Sum in C Programming with Solution: A Comprehensive Guide

Introduction

This problem is known as the “Two Sum” problem. In this article, we will delve into the intricacies of solving the Two Sum problem using the C programming language.

We will explore various techniques and provide step-by-step solutions to help you master this problem-solving challenge.

Also Read: Getchar and Putchar in C: A Comprehensive Guide

In the world of programming, problem-solving is an essential skill.

One common problem that often arises is finding the two numbers in an array that sum up to a given target value.

Two Sum in C Programming with Solution Explained

Two Sum: What is it?

Before we dive into the solution, let’s first understand the problem itself.

The Two Sum problem involves finding two distinct elements in an array whose sum equals a given target value.

Also Read: C Program to Find the Inverse of 2×2 Matrix

The task is to return the indices of these two numbers as the output. If no such pair exists, the algorithm should return an appropriate message.

Approach 1: Brute Force

One straightforward approach to solving the Two Sum problem is by using brute force.

This method involves checking every possible pair of numbers in the array and comparing their sums to the target value.

Also Read: C Program to Copy the Contents of One File into Another File

Here’s how it can be implemented in C programming:

#include <stdio.h>

void twoSum(int arr[], int size, int target) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] + arr[j] == target) {
                printf("Indices: %d, %d\n", i, j);
                return;
            }
        }
    }
    printf("No such pair exists.\n");
}

int main() {
    int arr[] = {2, 7, 11, 15};
    int target = 9;
    int size = sizeof(arr) / sizeof(arr[0]);

    twoSum(arr, size, target);

    return 0;
}

Approach 2: Using Hash Table

While the brute force approach works, it is not the most efficient solution, especially for larger arrays.

A more optimized approach involves using a hash table to store the elements and their indices.

Also Read: Best 5 Programs on Fibonacci Series in C

This allows for constant-time lookups when searching for the complement of a given number.

Let’s take a look at the implementation:

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

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

Node* createNode(int key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

void insert(Node* hashTable[], int key, int value) {
    int index = abs(key) % 1000;
    if (hashTable[index] == NULL) {
        hashTable[index] = createNode(key, value);
    } else {
        Node* newNode = createNode(key, value);
        newNode->next = hashTable[index];
        hashTable[index] = newNode;
    }
}

int search(Node* hashTable[], int key) {
    int index = abs(key) % 1000;
    Node* currentNode = hashTable[index];
    while (currentNode != NULL) {
        if (currentNode->key == key) {
            return currentNode->value;
        }
        currentNode = currentNode->next;
    }
    return -1;
}

void twoSum(int arr[], int size, int target) {
    Node* hashTable[1000] = {NULL};

    for (int i = 0; i < size; i++) {
        int complement = target - arr[i];
        int complementIndex = search(hashTable, complement);
        if (complementIndex != -1) {
            printf("Indices: %d, %d\n", complementIndex, i);
            return;
        }
        insert(hashTable, arr[i], i);
    }
    printf("No such pair exists.\n");
}

int main() {
    int arr[] = {2, 7, 11, 15};
    int target = 9;
    int size = sizeof(arr) / sizeof(arr[0]);

    twoSum(arr, size, target);

    return 0;
}

Frequently Asked Questions (FAQs)

Conclusion

In conclusion, the Two Sum problem in C programming can be efficiently solved using various approaches.

We explored the brute force method and the hash table approach, highlighting their implementations and time complexities.

The hash table approach offers a significant improvement in efficiency, making it the preferred choice for larger arrays.

By understanding and mastering these solutions, you’ll be better equipped to tackle similar problem-solving challenges in the world of programming.

Remember, problem-solving is a skill that improves with practice, so keep challenging yourself with new programming puzzles and projects. Happy coding!